0787-cheapest-flights-within-k-stops.js

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
 var findCheapestPrice = function (n, flights, src, dst, K) {
    const { graph, seen, minHeap } = buildGraph(n, flights, src, dst, K);

    return search(graph, src, dst, seen, minHeap);
};

var initGraph = (n) => ({
    graph: new Array(n).fill().map(() => []),
    seen: new Map(),
    minHeap: new MinPriorityQueue(),
})

var buildGraph = (n, flights, src, dst, K) => {
    const { graph, seen, minHeap } = initGraph(n);

    for (const [ src, dst, cost ] of flights) {
        graph[src].push([ dst, cost ]);
    }

    const priority = 0;
    const node = [ priority, src, (K + 1) ];

    minHeap.enqueue(node, priority);

    return { graph, seen, minHeap };
}

const search = (graph, src, dst, seen, minHeap) => {
    while (!minHeap.isEmpty()) {
        const [ cost, city, stops ] = minHeap.dequeue().element;

        seen.set(city, stops);

        const isTarget = (city === dst);
        if (isTarget) return cost;

        const canSkip = (stops <= 0);
        if (canSkip) continue;

        checkNeighbors(graph, cost, city, stops, seen, minHeap);
    }

    return -1;
}

var checkNeighbors = (graph, cost, city, stops, seen, minHeap) => {
    for (let [ nextCity, nextCost ] of graph[city]) {
        const hasSeen = (seen.has(nextCity) && ((stops - 1) <= seen.get(nextCity)));
        if (hasSeen) continue;

        const priority = (cost + nextCost)
        const node = [ priority, nextCity, (stops - 1)];

        minHeap.enqueue(node, priority);
    }
}