spfa 入门

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;//节点最大值
const int inf=1000000000;//边权最大值
struct node{
    int nxt,val;//下一条边编号，这条边的值
};
int n,m,s;//节点数，边数，源点
int p[maxn],d[maxn];//经过标记，长度
vector<node>e[maxn];//vector代替邻接表
queue<int>q;//queue优化
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        node tmp;tmp.nxt=y;tmp.val=z;
        //新建边，边权为z，边编号为y
        e[x].push_back(tmp);
        //加入x的vector
    }
    for(int i=1;i<=n;i++)
        d[i]=inf;
    //全体初始最大化
    d[s]=0;q.push(s);p[s]=1;
    //初始化源点
    while(!q.empty()){//直到队列不为空
        int x=q.front();//取队头
        q.pop();//对头出队
        for(int i=0;i<e[x].size();i++){
            //循环vector[e[x]]的每一条边
            int u=e[x][i].nxt,v=e[x][i].val;
            //u为e[x][i]的编号，v为e[x][i]的权值
            if(d[u]>d[x]+v){
                d[u]=d[x]+v;//如果d[u]不如d[x]+v短，则更改d[u]的权
                if(!p[u]){
                    q.push(u);//u入队
                    p[u]=1;//标记u被经过
                }           
            }       
        }
        p[x]=0;//标记p[x]重置为0
    }
    for(int i=1;i<=n;i++)
        if(d[i]<inf)
            printf("%d ",d[i]);
        else 
            printf("2147483647 ");
    //输出
    return 0;
}

spfa

原文：https://www.cnblogs.com/yangxuejian/p/10759317.html