dijkstra算法堆优化

#include <queue>
using namespace std;
#define INF 9999999999999
typedef long long  ll;
typedef struct {
    int u,v,w,nxt;
}edge;
edge e[500010];
int head[100010];
int cnt = 0;
void addedge(int u,int v,int w){
    e[++cnt] = {u,v,w,head[u]};
    head[u] = cnt;
}
int n,m,s;
ll dis[100010];
struct node{
    ll u,d;
    bool operator <(const node&rhs)const{
        return d>rhs.d;
    }
};
void dijkstra(){
    for (int i =1;i<=n;i++)
        dis[i] = INF;
    dis[s] = 0;
    priority_queue<node> q;
    q.push((node){s,0});
    while(!q.empty()){
        node flag = q.top();
        q.pop();
        ll u  = flag.u,d = flag.d;
        if(d!=dis[u]) continue;
        for (int i = head[u];i;i=e[i].nxt){
            int v = e[i].v,w = e[i].w;
            if(dis[v]>dis[u]+w){
                dis[v] = dis[u]+w;
                q.push((node){v,dis[v]});
            }
        }
    }
}
int main(){
    while(~scanf("%d %d ",&n,&m)){
        for (int i = 1;i<=m;i++){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            addedge(a,b,c);
        }
        s = 1;
        dijkstra();
        for (int i = 1;i<=n;i++){
            if(dis[i] == INF) printf("-1 ");
            else  printf("%lld ",dis[i]);
        }
        printf("n");
        }
    return 0;
}