This is a shortest path problem with an extra constraint on path length. We need the cheapest route between two cities, but the route may use at most k intermediate stops, which means at most k + 1 edges. Standard shortest path algorithms like Dijkstra's find the cheapest path regardless of how many edges it uses. Here, a longer path might be cheaper, but we can't take it if it exceeds the stop limit.

So the cost to reach a city is not enough information on its own. We also need to know how many flights were spent getting there. A city might be reachable cheaply with 5 stops, but if k = 2, that path is useless to us.

One way to track both is to explore paths level by level, where each level represents one more flight taken, and stop after k + 1 levels. BFS with level tracking and a modified Bellman-Ford both follow this structure. A third option keeps Dijkstra's cheapest-first order but adds the flight count to the search state.

Key Constraints:

Intuition

BFS explores paths level by level. Treat each level as one additional flight: after processing level 0, all direct flights from the source have been considered; after level 1, all paths with one stop; and so on. Processing ends after level k, which corresponds to k + 1 flights, or k stops.

At each level, every city whose cost improved in the previous level extends its paths by one more flight, and the cheapest known cost to reach each city gets updated. The comparisons must read the costs from the start of the current level, not values written during the level itself. Otherwise updates could chain within a single level, a path would gain two or more flights in one round, and the stop limit would be violated. So each level writes its updates to a copy of the cost array and swaps the copy in once the level is done.

Extending only from cities that improved in the previous level is enough for correctness. If a city's best cost using i + 1 flights beats its best cost using i flights, the last flight of that path leaves a city whose cost improved at level i. Cities whose costs did not change have already had all their outgoing flights relaxed at the same values in an earlier level.

Algorithm

Example Walkthrough

Code

Bellman-Ford produces the same level-by-level relaxation without an adjacency list or a frontier. It sweeps the raw edge list k + 1 times.

Intuition

Bellman-Ford finds shortest paths by relaxing every edge repeatedly. After iteration i, the dist array holds the shortest paths that use at most i + 1 edges. The standard version runs n - 1 iterations to cover every possible path length. Running exactly k + 1 iterations instead caps paths at k + 1 edges, which is the k-stop limit.

One adjustment is required. In standard Bellman-Ford, an update made early in an iteration can feed into a later relaxation within the same iteration, letting a path grow by several edges in one pass. That is harmless when the iteration count covers all path lengths, but here it would break the edge cap. So each iteration reads from a snapshot of the previous iteration's distances and writes to the current array. Each relaxation then extends a path by exactly one edge, the at-most-i+1-edges invariant holds after every iteration, and after k + 1 iterations dist[dst] is the cheapest cost using at most k + 1 edges.

Algorithm

Example Walkthrough

Code

Both approaches keep sweeping levels up to the k + 1 limit even after the destination's cost has settled. Dijkstra's algorithm explores states cheapest-first instead and can return the moment the destination comes off the heap.

Intuition

Dijkstra's algorithm pops nodes in non-decreasing cost order, so the first pop of the destination yields its cheapest cost. Applied directly to this problem it ignores the stop limit: in Example 1 it would return the 400-cost route 0 → 1 → 2 → 3 even though that route uses two stops and k = 1. Rejecting long paths with a visited set does not fix it either, because the cheapest way to reach an intermediate city may use too many flights, and finalizing that city blocks a pricier route that still has flights to spare.

The fix is to widen the search state. Each heap entry is (cost, city, flights taken), still ordered by cost, and a city may appear with several different flight counts. A popped state whose flight count exceeds k is discarded: it has arrived somewhere other than the destination and cannot board another flight. Because pops occur in non-decreasing cost order, the first time the destination pops there is no cheaper route within the budget, so its cost is the answer.

One pruning step keeps the heap manageable. A bestFlights array records the fewest flights among the states already expanded for each city. When a state pops with at least that many flights, an earlier expansion of the same city had cost no greater (pop order) and flights no greater, so every continuation of the current state is matched or beaten by a continuation of the earlier one, and the state can be dropped. Each expansion records a strictly smaller flight count, so a city is expanded at most k + 1 times.

Algorithm

Example Walkthrough

The trace uses Example 1: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1. The array shows bestFlights; heap states appear in the step labels as (cost, city, flights).

The discarded state at city 2 is the route 0 → 1 → 2 costing 200. It is the cheapest way to reach city 2, but with two flights spent it cannot continue, so the pricier 0 → 1 → 3 route popped next provides the answer.

Code