Cheapest, but with a limit
Find the cheapest trip that uses at most k stops by improving all prices in rounds, one more road per round. About 16 minutes.
Prices that improve in rounds
Suppose a trip may use at most k stops, which means at most k + 1 flights. A cheapest-first search doesn't respect that, because it might find a cheap route using many flights before a pricier route with few.
Instead, think in rounds. Before any round, only the start has a price, 0. In each round, look at every flight once: if the place it leaves had a price, see whether flying from there gives its destination a lower price than it currently has. After round r, every price uses at most r flights.
prices = dist[:] # a copy: use last round only
- round
- 0
Before any flight, only city 0 has a price: 0.
The copy matters
Notice we read from dist but write into a copy, nxt. If we wrote straight into dist, a flight processed later in the same round could use a price that an earlier flight had just improved. That route would take two flights in a single round, and the stop limit would stop meaning anything.
This idea is called the Bellman-Ford method. It is slower than the heap search, taking rounds times flights, but it handles an edge limit, and it also works when some prices are negative.
A trip may have at most 2 stops. How many rounds of improving prices do you run?
- A3, because 2 stops means 3 flights
- B2, one per stop
- CUntil no price changes
Show the answer
3, because 2 stops means 3 flights. Stops sit between flights, so k stops allow k + 1 flights, one per round.
Cheapest with at most k stops
There are n cities numbered 0 to n − 1. flights[i] = [from, to, price] is a one-way flight. Return the cheapest price of a trip from city src to city dst that has at most k stops (so at most k + 1 flights), or -1 if there is no such trip.
n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 2, 500], [1, 3, 600]], src = 0, dst = 3, k = 1 → 600
1 ≤ n ≤ 100 · 0 ≤ flights ≤ 5,000 · 1 ≤ price ≤ 10,000 · 0 ≤ k < n