Description
Find the lowest price from src to dst using directed flights with at most k intermediate stops. Return -1 if unreachable within that limit. Flight prices are positive.
Solution
def find_cheapest_price(n, flights, src, dst, k):
distance = [float("inf")] * n
distance[src] = 0
for _ in range(k + 1):
next_distance = distance.copy()
for source, target, cost in flights:
next_distance[target] = min(next_distance[target], distance[source] + cost)
distance = next_distance
return -1 if distance[dst] == float("inf") else distance[dst]Examples
Example 1
- Input
[4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1]- Output
700
The cheaper three-flight route exceeds one stop.
Example 2
- Input
[3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1]- Output
200
One stop allows the two-flight route.
Example 3
- Input
[3,[[0,1,100],[1,2,100]],0,2,0]- Output
-1
There is no direct flight to the destination.
Approach
Perform k + 1 Bellman-Ford rounds. Each round reads the previous distance array and writes a copy, so it adds at most one flight to a path. Never relax from the partially updated array.
Time & space
O((k + 1)(V + E)) time and O(V) auxiliary space, where V is city count and E is flight count.