迪杰斯特拉 参考代码

typedef long long LL;
const int maxn = 100000 + 100;
struct Node {
    int pos;
    LL dis;
    // 无参与有参构造函数
    Node() {}
    Node(int pos, LL dis) : pos(pos), dis(dis) {}
};

// 重载 Node 的小于运算符
// 由于 priority_queue 默认为大顶堆，这里将 dis 的比较取反，可以得到关于 Node 的小顶堆
bool operator<(const Node &a, const Node &b) {
    return a.dis > b.dis;
}

bool vis[maxn];             // 标记节点是否已确认最短路径，非常重要，没有这个判断可能 TLE
LL dis[maxn];               // 记录最短距离
vector<Node> G[maxn];       // 图的邻接表结构
priority_queue<Node> que;   // 用于快速得到距离最短的节点的优先队列

void dij(int s) {
    // 将所有节点的距离初始化为“无穷大”
    // 该“无穷大”值可以与其它较小值相加且不发生溢出
    memset(dis, 0x3f, sizeof(dis));
    // 初始化起点距离为 0
    que.push(Node(s, 0));
    dis[s] = 0;

    while (!que.empty()) {
        // 从优先队列中取出距离最短的点
        Node tmp = que.top();
        que.pop();
        // 如果已取出过，直接 continue，不要再重复处理，不然会被极端数据卡 TLE
        if (vis[tmp.pos]) {
            continue;
        }
        vis[tmp.pos] = true;

        for (Node &node : G[tmp.pos]) {
            if (dis[node.pos] > tmp.dis + node.dis) {
                // 能通过 tmp.pos 走到 node.pos，且距离更短，就更新距离，且入堆
                dis[node.pos] = tmp.dis + node.dis;
                que.push(Node(node.pos, dis[node.pos]));
            }
        }
    }
}