787. Cheapest Flights Within K Stops

Practice Cheapest Flights Within K Stops for free on NudgeCode: Medium, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

There are n cities labeled 0 to n - 1. Each flights[i] = [from, to, price] is a one-way flight. Return the cheapest price to travel from src to dst with at most k stops in between (so at most k + 1 flights), or -1 if no such route exists.

Example

n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],
src = 0, dst = 3, k = 1  ->  700

(0 -> 1 -> 2 -> 3 costs 400 but needs 2 stops.)

Constraints

• 1 <= n <= 100
• 0 <= flights.length <= n * (n - 1)
• from != to, 1 <= price <= 10^4, no flight repeats
• 0 <= src, dst, k < n, src != dst