题解 | 【模板】单源最短路2

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

class Node {
    constructor(id) {
        this.id = id;
        this.next = [];
        this.cost = Infinity;
        this.status = false;
    }
    addNext(next, cost) {
        this.next.push({ next, cost });
    }
}

void (async function () {
    const [maxNode, links] = (await readline()).split(" ").map(Number);
    const nodesMap = new Map();
    nodesMap.set(1, new Node(1));
    nodesMap.get(1).cost = 0;

    // 初始化优先队列，使用数组模拟最小堆
    const priorityQueue = [];
    priorityQueue.push([nodesMap.get(1), 0]);

    // 最小堆辅助函数
    function heapify(arr, index) {
        let left = 2 * index + 1;
        let right = 2 * index + 2;
        let smallest = index;

        if (left < arr.length && arr[left][1] < arr[smallest][1]) {
            smallest = left;
        }
        if (right < arr.length && arr[right][1] < arr[smallest][1]) {
            smallest = right;
        }
        if (smallest !== index) {
            [arr[index], arr[smallest]] = [arr[smallest], arr[index]];
            heapify(arr, smallest);
        }
    }

    function addToHeap(node, cost) {
        priorityQueue.push([node, cost]);
        let i = priorityQueue.length - 1;
        while (i > 0 && priorityQueue[Math.floor((i - 1) / 2)][1] > priorityQueue[i][1]) {
            [priorityQueue[i], priorityQueue[Math.floor((i - 1) / 2)]] = [priorityQueue[Math.floor((i - 1) / 2)], priorityQueue[i]];
            i = Math.floor((i - 1) / 2);
        }
    }

    for (let i = 1; i <= links; i++) {
        const [start, end, cost] = (await readline()).split(" ").map(Number);
        if (!nodesMap.has(start)) {
            nodesMap.set(start, new Node(start));
        }
        if (!nodesMap.has(end)) {
            nodesMap.set(end, new Node(end));
        }
        nodesMap.get(start).addNext(end, cost);
        nodesMap.get(end).addNext(start, cost);
    }

    while (priorityQueue.length > 0) {
        // 取出堆顶元素
        let minElement = priorityQueue[0];
        priorityQueue[0] = priorityQueue[priorityQueue.length - 1];
        priorityQueue.pop();
        heapify(priorityQueue, 0);

        const [u, currentCost] = minElement;

        if (u.status) continue;
        u.status = true;

        for (const { next: v, cost: edgeCost } of u.next) {
            if (nodesMap.get(v).cost > currentCost + edgeCost) {
                nodesMap.get(v).cost = currentCost + edgeCost;
                addToHeap(nodesMap.get(v), nodesMap.get(v).cost);
            }
        }
    }

    rl.close();
    console.log(nodesMap.get(maxNode)?.cost === Infinity ? -1 : nodesMap.get(maxNode)?.cost || -1);
})();

思路其实都大差不差，主要是代码方面的时间优化，还有一些边界情况的考虑。

Dijkstra算法，核心就是用一个优先队列来存储后续需要进行对比的任务，然后方便拿取数据用一个node class来存储数据及状态。