【模板】SPFA

#include<bits/stdc++.h>
#define MAX 10002
#define INF 2147483647
using namespace std;
int n,m,d[MAX],s;
bool b[MAX];
struct Edge
{
    int id;
    int c;
    Edge(int x,int y){id=x,c=y;}
};
vector<Edge>G[MAX];
void SPFA()
{
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    b[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        b[u]=0;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i].id,c2=G[u][i].c;
            if(d[v]>d[u]+c2)
            {
                d[v]=d[u]+c2;
                if(!b[v])
                {
                    b[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int a1,a2,a3;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a1,&a2,&a3);
        G[a1].push_back(Edge(a2,a3));
    }
    SPFA();
    for(int i=1;i<=n;i++)printf("%d ",d[i]);
    return 0;
}