Cheapest Flights Within K Stops

The problem

Implement `findCheapestPrice(n, flights, src, dst, k)` where `flights[i] = [from, to, price]` is a directed edge. Return the cheapest price from `src` to `dst` using at most `k` intermediate stops (i.e. at most `k + 1` edges), or `-1` if no such route exists.

`n = 4, flights = [[0,1,200],[1,2,100],[1,3,300],[2,3,100]], src = 0, dst = 3, k = 1` returns `500`, not `400` — `0 -> 1 -> 2 -> 3` is cheaper overall but takes `2` stops, one more than `k` allows, so `0 -> 1 -> 3` (`1` stop, cost `500`) is what actually qualifies.

The approach

The reason `networkDelayTime`'s `visited` Set can't just be reused here is the whole problem: there, once a node's cheapest price was popped, no other path to it could ever matter, since taking more edges to reach it is never disallowed. Here edges run out — the cheapest price to some intermediate node might only be reachable by a path that's already used up too many stops to be useful, while a pricier arrival at that same node, reached in fewer stops, is the one that still has stops left to reach `dst`. 'Finalize on first visit' is exactly the assumption that breaks.

Bellman-Ford sidesteps that by not finalizing anything — it relaxes every edge in `flights` a fixed number of times, and the round count *is* the stop limit: after `r` rounds, `prices[node]` holds the cheapest cost reachable using at most `r` edges. Running exactly `k + 1` rounds (one more than the stop count, since `k` stops means `k + 1` edges) turns the constraint into a loop bound instead of a piece of state carried per node.

Each round has to relax against a snapshot of the *previous* round's prices (`nextPrices = [...prices]`, reading `prices[from]` while writing `nextPrices[to]`), not against prices already updated this round — relaxing against same-round updates would let one round silently chain two edges together, sneaking a path an extra stop for free without it ever getting counted.

The solution

class Solution {
    /**
     * @param {number} n
     * @param {number[][]} flights
     * @param {number} src
     * @param {number} dst
     * @param {number} k
     * @return {number}
     */
    findCheapestPrice(n, flights, src, dst, k) {
        let prices = new Array(n).fill(Infinity);
        prices[src] = 0;

        for (let stop = 0; stop <= k; stop++) {
            const nextPrices = [...prices];

            for (const [from, to, price] of flights) {
                if (prices[from] !== Infinity && prices[from] + price < nextPrices[to]) {
                    nextPrices[to] = prices[from] + price;
                }
            }

            prices = nextPrices;
        }

        return prices[dst] === Infinity ? -1 : prices[dst];
    }
}

Time O(k * E)Space O(n)