Cheapest flights within K stops

Return the cheapest price from src to dst using at most k stops (k + 1 flights), or -1.

Before you code

Plain Dijkstra keeps only the cheapest price per city and forgets how many flights were used, so it can discard a pricier route with fewer stops that was needed. Bellman-Ford's rounds count edges.

Hints

1. Run k + 1 rounds. In each, start from a copy of the previous prices.
2. For every flight (u, v, w), update new[v] = min(new[v], prev[u] + w).
3. Reading only prev ensures each round adds at most one flight.

Production & complexity notes

When solving Cheapest flights within K stops on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Negative edges and Bellman-Ford to reinforce the underlying pattern.

What it practices

Bellman-Ford rounds as a hop limit, from Negative edges and Bellman-Ford.