Cheapest Flights Within K Stops – Solution & Complexity

• At most k stops means at most k + 1 actual flight edges.
• So you never need routes longer than k + 1 relaxations, even if the graph contains cycles.

• Explore all routes from src to dst with DFS while tracking how many stops remain.
• That works for tiny graphs, but the branching factor makes it explode quickly.

• Let prices[v] mean the cheapest known cost to reach city v using at most the previous number of edges.
• On each of k + 1 rounds, copy the current array and relax every directed flight into the copy. Using the copy is crucial: it prevents one round from chaining together more than one new edge.
• After k + 1 rounds, prices[dst] is the best cost using at most k + 1 edges, exactly matching the stop limit.

A copied distance array per round enforces the stop budget while keeping the implementation compact.

• If you relax into the same array you are reading from, one round might accidentally use two newly updated edges, violating the stop budget.
• Using nextPrices guarantees round r only represents routes with at most r edges.
• This is the same core Bellman-Ford idea, just stopped early because the interview problem limits the route length.