SPFA模板

（………………）#include<bits/stdc++.h>
const int maxn=10000015;
using namespace std;
int n,m,s;
int dis[maxn];
//链式前向星 
const int N=10005,M=5000005;
int e,first[N],nex[M],v[M],w[M];
bool inq[N];
void AddEdge(int U,int V,int W){//添加边 
    v[++e]=V;
    w[e]=W;
    nex[e]=first[U];
    first[U]=e;
}
void spfa()
{
    queue<int>q;
    for(int i=1; i<=n; i++) 
        dis[i]=2147483647; 
    dis[s]=0;
    q.push(s);//将s加入队列末尾 
    while(!q.empty()){//检测队列非空 
        int U=q.front();//取队头的元素
        for(int i=first[U];i;i=nex[i])
        {
            if(dis[v[i]]>dis[U]+w[i])
            {
                dis[v[i]]=dis[U]+w[i];
                if(!inq[v[i]])
                {
                    q.push(v[i]);
                    inq[v[i]]=true;
                }
            }
        }
        q.pop();//从队头删除元素 
        inq[U]=false;
    }
}
int main()
{
  scanf("%d%d%d",&n,&m,&s);
  for(int i=1; i<=m; i++)
  {
    int f,g,w;
    scanf("%d%d%d",&f,&g,&w); 
    AddEdge(f,g,w); //建图，有向图连一次边就可以了
  }
  spfa(); //开始跑spfa
  for(int i=1; i<=n; i++)
    if(s==i) printf("0 "); //如果是回到自己，直接输出0
      else printf("%d ",dis[i]); //否则打印最短距离
  return 0;
} //结束