Graph State Space

// Cheapest Flights Within K Stops — Dijkstra on (cost, node, stops_remaining)
function cheapestFlights(n, flights, src, dst, k) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v, w] of flights) adj[u].push([v, w]);

    // dist[node][stops] = min cost to reach node with stops remaining
    const dist = Array.from({length: n}, () => new Array(k+2).fill(Infinity));
    dist[src][k+1] = 0;

    // Min-heap: [cost, node, stops_remaining]
    const heap = [[0, src, k+1]];

    while (heap.length) {
        heap.sort((a,b) => a[0]-b[0]); // simple priority queue
        const [cost, u, stops] = heap.shift();
        if (u === dst) return cost;
        if (stops === 0) continue;
        for (const [v, w] of adj[u]) {
            const newCost = cost + w;
            if (newCost < dist[v][stops-1]) {
                dist[v][stops-1] = newCost;
                heap.push([newCost, v, stops-1]);
            }
        }
    }
    return -1;
}