这是一个关于SPFA的题解。。（Dijkstra不太会。。）

由于邻接表太烦（不会），所以就直接写个vector来存边的关系，

然后用v[f][i].first表示f点连出去的第i个点的编号，v[f][i].second表示

f点连出去的第i条边的权值。所以，每次判断一下是否经过点i更优，并且更新。

scanf("%lld%lld%lld",&n,&m,&s);

while(m--){

     scanf("%lld%lld%lld",&x,&y,&z);

     v[x].push_back(make_pair(y,z));//建图，将边的关系存入v数组 

}   

for(int i=1;i<=n;i++)d[i]=2147483647;

vis[s]=1;//将s点标为已入队 

d[s]=0;//s到自己的距离当然是0 

l[0]=s;//s点入队 

int h=0,t=1;//注意队列数组开大一些，因为每个点入队可能有好几次 

while(h<t){//当队列中还有点时继续循环 

    int f=l[h++];vis[f]=0;//初始化，将队头的点进行操作 

    for(int i=0;i<v[f].size();i++)//枚举每条边 

    if(d[v[f][i].first]>d[f]+v[f][i].second){//判断是否为更优 

        d[v[f][i].first]=d[f]+v[f][i].second;//更新 

        if(!vis[v[f][i].first]) vis[v[f][i].first]=1,l[t++]=v[f][i].first;//更新后标为已入队 

    }

}

for(int i=1;i<=n;i++)

printf("%lld ",d[i]);