spfa（模板）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
const int MAXN = 10005,MAXM = 500005;

struct Edge{
    int nxt,to,v;
}edge[MAXM];

int n,m,cnt,st,head[MAXN],dis[MAXN];
bool vis[MAXN];
queue<int> q;

inline void add(int bg,int ed,int w){
    edge[++cnt].to=ed;
    edge[cnt].v=w;
    edge[cnt].nxt=head[bg];
    head[bg]=cnt;
}

inline void spfa(){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;vis[st]=1;
    q.push(st);
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(register int i=head[x];i;i=edge[i].nxt){
            int u=edge[i].to;
            if(dis[u]>dis[x]+edge[i].v){
                dis[u]=dis[x]+edge[i].v;
                if(!vis[u])
                    q.push(u),vis[u]=1;
            }
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&st);
    for(register int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }spfa();
    for(register int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}