Hints — p64 Cheapest Flights Within K Stops

Hint 1. “K stops” = K intermediate cities = K+1 edges. A direct flight is 0 stops.

Hint 2. Dijkstra is the WRONG choice here. With a hop-limit, the cheapest cumulative cost to a node may use too many edges to extend further, while a more expensive earlier-stage path with fewer edges could lead to a cheaper full solution. Construct a small counterexample to convince yourself.

Hint 3. Bellman-Ford bounded to K+1 iterations works. Invariant: after iteration i, dist[v] = cheapest cost to reach v using ≤ i edges. Run K+1 times.

Hint 4. Critical: use TWO arrays (prev and curr). At each iteration, curr = prev.copy(), then relax edges into curr using prev[u]. Updating in-place lets a single iteration chain multiple edges — wrong number of stops.

Hint 5. Alternative: BFS/Dijkstra over an extended state (node, stops_used). Push (cost, u, k); relax to (v, k+1) if allowed. Slightly more code but no prev.copy() discipline needed.

If stuck: see solution.py.