Cheapest Flights Within K Stops
Part of Practice: Shortest & Cheapest
There are n cities and a list of one-way flights, each [from, to, price]. Given a start city src, a destination dst, and an integer k, return the cheapest total price to fly from src to dst using at most k intermediate stops — that is, at most k + 1 flights. If no such route exists, return -1.
Constraints that matter: up to 100 cities and k < n, so an O(k · E) algorithm is fast. The stop limit is the whole difficulty — it breaks plain greedy shortest-path reasoning.
Examples
- Input:
- n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
- Output:
- 200
One stop allowed: fly 0 to 1 to 2 for 200 instead of the direct flight at 500.
- Input:
- n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
- Output:
- 500
Zero stops means direct flights only, so the 500 flight is the only option.
- 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
With one stop the best is 0 to 1 to 3 for 700. The cheaper-looking route through 2 needs two stops.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.