The Dijkstra card keeps a heap and settles one node at a time, by cost. This card has no heap. It runs rounds, and round i adds one more flight to every route.

Why this is needed: Dijkstra settles a node by its cost alone, and it cannot count flights. In Cheapest Flights Within K Stops (LC 787), the cheapest route overall may use too many stops. For the example in the board below, Dijkstra would find the route 0 -> 1 -> 2 -> 3 at price 400. It uses 3 flights, but k = 1 allows only 2 flights. The right answer is 700.

So each round keeps a list of prices by number of flights. After round i, prices[v] is the cheapest price of a route from src to v with at most i flights. The list has one number per city, so the cost of a round is small.

A round reads prices and writes tmp_prices. This keeps the rounds apart, so one round can add exactly one flight.

The board runs bellman_ford_k_stops with n = 4, src = 0, dst = 3 and k = 1. One stop means at most 2 flights, so there are 2 rounds.

Round 1 starts with prices = [0, inf, inf, inf]. Only flight 0 -> 1 has a reachable start, so tmp_prices[1] = 100. The result is [0, 100, inf, inf].

Round 2 relaxes flight 1 -> 2 to 200 and flight 1 -> 3 to 700. Flight 2 -> 3 is skipped, because prices[2] was still inf at the end of round 1. The result is [0, 100, 200, 700], and the answer is 700.

The step marked as a trap shows what in-place writing would do. tmp_prices[2] = 200 is already set in round 2, so flight 2 -> 3 would give 400. That route has 3 flights, which k = 1 does not allow.

tmp_prices = prices does not copy the list. It gives the same list a second name. A price written in a round is then read again in the same round, so one round can add several flights.

For the trace above, writing in place returns 400 and not 700. Flight 0 -> 1 sets prices[1] = 100, flight 1 -> 2 then sets prices[2] = 200, and flight 2 -> 3 sets prices[3] = 400. All three happen in one round.

The second trap is the round count. k stops allow k + 1 flights, so run range(k + 1) rounds. With range(k) the same example returns -1, because the route to city 3 needs both flights.

Last, if prices[dst] is still inf at the end, return -1. For n = 3, flights = [[0, 1, 100]], src = 0, dst = 2 and k = 1, no route exists.

Dijkstra needs every weight to be zero or more. A rounds method does not settle a node early, so a negative weight is fine here. A later round can still lower any price.

Example: edges = [[0, 1, 2], [0, 2, 3], [2, 1, -2]] from city 0 to city 1. A Dijkstra that never revisits a settled node returns 2. Bellman-Ford with 2 rounds returns 1, through the route 0 -> 2 -> 1 that costs 3 - 2. With 1 round it still returns 2, as it should for a cap of one flight.

Each round copies prices and reads every flight once, so the time is O(k * (V + E)) and the space is O(V). The board has 5 flights and 2 rounds, so it makes 10 flight checks.

With no cap, run n - 1 rounds. A route without a repeated city has at most n - 1 flights. This costs O(V * E), which is slower than Dijkstra. That is the price of allowing negative weights.