504. Cheapest Flights Within K Stops
There are n cities numbered 0 to n - 1 connected by m one-way flights. Your function receives n, the flight list flights where flights[i] = [from, to, price] describes a direct flight, a starting city src, a destination dst, and an integer k.
Return the lowest total price of any route from src to dst that makes at most k stops in intermediate cities — that is, a route using at most k + 1 flights. If dst cannot be reached within that limit, return -1.
Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: With at most 1 stop the best route is 0 → 1 → 3, costing 100 + 600 = 700. The cheaper route 0 → 1 → 2 → 3 (400) is not allowed because it makes 2 stops.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: One stop is allowed, so 0 → 1 → 2 costing 200 beats the direct flight at 500.
Constraints:
- 2 ≤ n ≤ 100
- 0 ≤ m ≤ 600; no duplicate flights and no flight from a city to itself
- flights[i] = [from, to, price] with 1 ≤ price ≤ 10⁴
- 0 ≤ src, dst < n, src ≠ dst, 0 ≤ k ≤ n - 1
Hints:
Plain Dijkstra with a visited set fails here: a partial route that costs more but has used fewer flights can still be the only one able to reach dst under the limit. Ask yourself what extra piece of information a search state needs.
Let dist_r[v] be the cheapest cost to reach v using at most r flights. Run k + 1 relaxation rounds over the edge list, each round reading only the previous round's values (Bellman-Ford, cut off early). Alternatively, run a min-heap search over (cost, city, flights used) states.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Expected output: 700