Cheapest Flights Within K Stops

There are n cities labeled 0 through n - 1 and directed flights flights[i] = [from_i, to_i, price_i]. Return the cheapest price from src to dst using at most k stops, where a stop is an intermediate city. If no such route exists, return -1.

Input / output

• Input: n: int, flights: int[][], src: int, dst: int, k: int
• Output: cheapest valid price, or -1 if unreachable under the stop limit

Examples

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 returns 700.
2. n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 returns 200.
3. The same graph with k = 0 returns 500 because only direct flights are allowed.

Constraints

• 1 <= n <= 100
• 0 <= flights.length <= n * (n - 1) / 2
• 0 <= from_i, to_i < n, from_i != to_i
• 1 <= price_i <= 10^4
• 0 <= k < n

Target complexity

• Aim for O(k * flights.length) time.

Hints

1. With at most k stops, any valid route uses at most k + 1 flight edges.
2. Bellman-Ford style relaxation works if each round is based on the previous round's distances, not partially updated ones from the same round.

Follow-up Why can a plain Dijkstra implementation return the wrong answer if it ignores how many stops were used to reach a city?