Cheapest Flights Within K Stops
Signals to notice
Brute force first
Try all paths with ≤ k+1 edges — exponential. Enumerates every possible route. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
Bellman-Ford with k+1 relaxation rounds. Or BFS with (cost, node, stops) states and a min-heap (modified Dijkstra). Each round relaxes all edges, but only for k+1 rounds. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
What must stay true
After i rounds of Bellman-Ford, the shortest paths using at most i edges are computed. Running k+1 rounds gives the answer with the stop constraint. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Easy way to go wrong
Using standard Dijkstra without the stop constraint — Dijkstra finds the cheapest path regardless of stops. You need to track stops as part of the state. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.