堆优化Dijkstra

#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#define MAXN 500005

struct Node {
    int u,dis;
    inline bool operator < (const Node& node) const {
        return dis > node.dis;
    }
};

std::priority_queue < Node > q;

struct edge {
    int u,v,w,next;
} G[MAXN<<1];

int head[MAXN],vis[MAXN],dis[MAXN];
int N,M,S,tot = 0;

inline void add(int u,int v,int w) {
    G[++tot].v = v; G[tot].w = w; G[tot].next = head[u]; head[u] = tot;
}

int main() {

    scanf("%d%d%d",&N,&M,&S);
    for(int i=1;i<=M;++i) {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        add(u,v,w); 
    }

    for(int i=1;i<=N;++i) dis[i] = 2147483647;
    dis[S] = 0; q.push( (Node){S,0} );

    while(!q.empty()) {
        
        int u = q.top().u; q.pop();
        if(vis[u]) continue; vis[u] = 1;
        for(int i=head[u];i;i=G[i].next) {
            int v = G[i].v; int w = G[i].w;
            if(dis[v]>dis[u]+w) q.push( (Node){v,dis[v]=dis[u]+w} );
        }
    }

    for(int i=1;i<=N;++i) printf("%d ",dis[i]);
    return 0;
}

模板 最短路径