There are n cities and a list of one-way flights where flights[i] = [from, to, price]. Find the cheapest price to travel from src to dst using at most `k` stops (a stop is an intermediate city, so at most k + 1 flights). Return -1 if no such route exists.
- 1 <= n <= 100
- 0 <= flights.length <= n * (n - 1) / 2
- 1 <= price <= 10^4
- No duplicate flights
- 0 <= src, dst, k < n, src != dst
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force explores every route with DFS up to k + 1 flights, which blows up exponentially. Dijkstra by price alone is wrong because a cheap route with too many stops can hide a slightly costlier valid one. Bellman-Ford fits naturally: after round i, cost[v] is the cheapest price to reach v using at most i flights. The catch is to relax from a snapshot of the previous round; otherwise one round could chain several flights and break the stop limit.
Algorithm
- Set
cost[src] = 0and every other city to infinity. - Repeat
k + 1times: copycostintonext. - For each flight
[u, v, p], ifcost[u]is finite, setnext[v] = min(next[v], cost[u] + p). - Replace
costwithnextat the end of the round. - Return
cost[dst], or -1 if it is still infinity.
O(k * E)Space: O(n)cost in place lets a single round use several flights, giving an answer that breaks the k stops rule.class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: INF = float('inf') cost = [INF] * n cost[src] = 0 for _ in range(k + 1): # at most k + 1 flights nxt = cost[:] # snapshot so each round adds one flight only for u, v, p in flights: if cost[u] != INF and cost[u] + p < nxt[v]: nxt[v] = cost[u] + p cost = nxt return -1 if cost[dst] == INF else cost[dst]