397. Cheapest Flights Within K Stops

Given n cities (0-indexed) and m directed flights (each u, v, price), a source, a destination, and a maximum number of stops k (so at most k+1 flights total), find the cheapest price to travel from source to destination within that limit. Print -1 if no such route exists.

Input: The first line contains an integer n, the number of cities. The second line contains an integer m, the number of directed flights. Each of the next m lines contains three space-separated integers u, v, and price. This is followed by a line with the source city, a line with the destination city, and a line with k, the maximum number of stops. Output: Print a single integer - the cheapest price from source to destination within k stops, or -1 if no such route exists.

1 <= n <= 1000, 0 <= k <= n

This is a direct, practical application of bounding Bellman-Ford's usual 'run until convergence' behavior - recognizing that CAPPING the round count directly enforces a maximum-path-length constraint is a valuable, reusable technique.

Find the cheapest way to travel between two cities, using at most a limited number of connecting flights. Brute force: Try every possible route from source to destination using at most k+1 flights directly, checking all combinations - this can be exponential in the worst case, when a bounded Bellman-Ford variant finds the answer in polynomial time. Optimised: Capping Bellman-Ford at EXACTLY (k+1) rounds (rather than running to full convergence) directly enforces the 'at most k+1 flights' constraint - using a SNAPSHOT of the PREVIOUS round's distances (rather than allowing updates within the same round to chain together) is the crucial detail preventing a single round from accidentally using MORE than one new edge per path.

Recursively explore every possible path from source to destination, at each city trying every outgoing flight and recursing with one fewer stop remaining, tracking the accumulated cost and taking the minimum over all completed paths. This visits paths repeatedly since the same (city, stops-remaining) state can be reached via many different routes, so the number of explored paths grows exponentially with the number of edges, but it is a straightforward and correct exhaustive search. Time: O(V^K) worst case Space: O(K)

Run the same recursive search as the brute force, but cache the best cost found for each (city, stops-remaining) pair so that once a state has been fully explored, any later path reaching the same city with the same stops budget reuses the cached answer instead of re-exploring the whole subtree. This top-down dynamic programming turns the exponential blow-up into a bounded number of distinct states (one per city per stops value), each expanded once across its outgoing edges. Time: O(n*k*avg_degree) Space: O(n*k)

Maintain a distance array initialized to infinity except source = 0, and perform exactly k+1 rounds of edge relaxation; crucially, each round relaxes every edge using a snapshot of the distances from before this round started (not values already updated in the current round), which enforces that a path uses at most one additional flight per round. After k+1 rounds, dist[destination] holds the cheapest cost using at most k+1 flights, or infinity if unreachable within that limit. This avoids exploring individual paths altogether and instead propagates the cheapest-cost frontier, giving a tight bound driven only by the number of edges and stops. Time: O(k*m) Space: O(n)

1. Use a Bellman-Ford VARIANT capped at exactly (k+1) rounds of relaxation, instead of running to full convergence. 2. Each round adds AT MOST one more flight to any path - relax every edge using a SNAPSHOT of distances from BEFORE this round started (not distances already updated earlier in the SAME round). 3. If the destination's distance is still infinity after (k+1) rounds, no route exists within the stop limit.

Time: O(k * m) - k+1 rounds, each relaxing all m edges. Space: O(n), for the distance array (plus O(n) for the snapshot copy each round).

k = 0 (only a direct flight allowed), no route existing within the stop limit (print -1), and n at its maximum of 1000 to confirm the capped Bellman-Ford runs efficiently.

Be ready to explain explicitly WHY using a snapshot (not live-updating distances) is essential - without it, a single round could incorrectly chain together multiple edge relaxations, silently violating the stop-count limit this problem specifically enforces.