No.A569 题解

题解,含注释

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,vis[2000005],d[2000005];
int e[2000005],h[2000005],ne[2000005],w[2000005],idx;
void add(int a,int b,int c){//从a去到b要花费c
    e[idx]=b;//终点
    w[idx]=c;//权值
    ne[idx]=h[a];//以a为起点的下一条边
    h[a]=idx++;//起点的边的编号
}
void dj(){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
    //结构体{距离,顶点}
    d[s]=0;
    que.push({0,s});
    while(que.size()){
        auto n1=que.top();//取队头
        que.pop();
        int x=n1.first;//距离
        int y=n1.second;//顶点
        if(vis[y]){
            continue;
        }
        vis[y]=1;
        for(int i=h[y];i!=-1;i=ne[i]){//链式前向星固定遍历写法
            int z=e[i];//终点
            int ww=w[i];
            if(vis[z]==0&&d[z]>x+ww){
                d[z]=x+ww;
                que.push({d[z],z});
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof h);
    memset(d,0x3f,sizeof d);
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dj();
    for(int i=1;i<=n;i++){
        if(d[i]==0x3f3f3f3f){
            printf("-1 ");
        }
        else{
            printf("%d ",d[i]);
        }
    }
    return 0;
}