Cheapest Flights Within K Stops

Problem

There are n airports numbered 0..n-1 and a list of one-way flights, where flights[i] = [from, to, price]. You want to travel from airport src to airport dst using at most k intermediate stops (so at most k + 1 flights). Return the lowest total price of such an itinerary, or -1 if no itinerary satisfies the stop limit.

• Up to a hundred airports and no more than one route between any ordered pair.
• Prices are positive and comfortably fit a normal int.
• src, dst, and k are all valid airport indices or stop counts for the given n, and src != dst.

Examples

• n = 4, flights = [[0,1,120],[1,2,130],[2,3,140],[0,3,800],[1,3,700]], src = 0, dst = 3, k = 1 → 800. The cheapest overall route 0→1→2→3 costs 390 but uses two stops; with only one stop allowed the direct flight at 800 wins over 0→1→3 at 820.
• n = 3, flights = [[0,1,80],[1,2,80],[0,2,300]], src = 0, dst = 2, k = 1 → 160. One stop at airport 1 is allowed.
• n = 3, flights = [[0,1,80],[1,2,80],[0,2,300]], src = 0, dst = 2, k = 0 → 300. No stops allowed, so only the direct flight counts.

Hints

1. Why does ordinary Dijkstra give the wrong answer on the first example? What information does it throw away when it finalizes a node?
2. Think of the answer as a function of two things: which airport you are at and how many flights you have taken.
3. Run k + 1 rounds of edge relaxation where each round only reads distances from the previous round (bounded Bellman-Ford), or BFS level by level with pruning.