The problem
There are n cities. Each [from, to, price] is a one-way flight.
Return the cheapest price from src to dst using at most k stops in between (so at most k + 1 flights), or −1 if there is no such route.
Examples
- 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
- Input
n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
- Output
200
- Input
n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0
- Output
500
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ price ≤ 10⁴
- At most one flight between any two cities in each direction.
- 0 ≤ src, dst, k < n, and src ≠ dst.
The idea
Dijkstra’s cheapest-first order ignores how many flights a route uses, and the cheapest route may have too many. Bellman–Ford counts them naturally: each round lets every route grow by one flight.
Start with src at 0 and everything else unreachable. Each round, for every flight u → v, see whether reaching u last round and then flying on is cheaper. Reading last round’s prices — a copy — is what keeps each round to exactly one extra flight. After k + 1 rounds, the price of dst is the cheapest with at most k stops.
- Time
- O(k · F) — F flights, k + 1 rounds
- Space
- O(n)
Solution · every language run against every case
class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: # Bellman-Ford, stopped after k + 1 rounds: after round r, cost[v] is the cheapest # way to v using at most r flights (at most r - 1 stops). cost = [float("inf")] * n cost[src] = 0 for _ in range(k + 1): before = cost[:] # read last round's costs, so one round adds only one flight for u, v, p in flights: if before[u] + p < cost[v]: cost[v] = before[u] + p return -1 if cost[dst] == float("inf") else cost[dst]