The problem
Given flights (u, v, price) and cities src, dst, find the cheapest route src → dst using at most k stops (k+1 edges), or −1 if none exists.
Stuck? Reveal hints one at a time
How to approach it
- 1Initialize cost array with Infinity, cost[src] = 0.
- 2Repeat k+1 times: copy the current costs, relax every flight (u, v, w) against the PREVIOUS round’s values, writing into the copy.
- 3Swap the copy in after each round — this caps path length at (round count) edges.
- 4Answer is cost[dst] after k+1 rounds, or −1 if still Infinity.
Key insight
Relaxing from a frozen previous-round snapshot is what enforces the stop limit — each round adds at most one edge to any path.
The solution
Watch out for
- Relaxing in place (no snapshot) lets one round chain multiple edges, silently breaking the stop limit.
- k stops means k+1 edges — off-by-one here is the most common wrong answer.