SPFA

知识梗概

使用SPFA的图中，不可以有负权回路。

模板（类似于BFS）

//创建一个不存在重复元素的队列（使用一个布尔型数组来辅助保证元素不重复）
queue<int>q;
bool sta[N];

void spfa(){
    //初始化dist数组，起点距离设置为0

    //起点入队，并将起点状态值设为true
    q.push(1);
    sta[1]=true;

    //队列不为空
    while(!q.empty()){
        //队首元素t出队,由于队首元素出队，所以将其状态值设置为false

        //使用t更新与之相关点
        for(...){
            if(dist[u]>dist[t]+w[i]){
                dist[u]=dist[t]+w[i];

                //如果点u的dist被更新，并且队列中没有u，将u入队，并改变其状态
                if(!sta[u]){
                    q.push(u);
                    sta[u]=true;}
            }
        }
    }
    if(dist[n]>0x3f3f3f3f/2) cout<<"impossible";
    else cout<<dist[n];
}

C++ 代码

#include<bits/stdc++.h>

using namespace std;
const int N=2e5+5;

int n,m,e[N],ne[N],h[N],idx,dist[N],w[N];
queue<int>q;
bool sta[N];


void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void spfa(){
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[1]=0;

    q.push(1);
    sta[1]=true;

    while(!q.empty()){
        int t=q.front();
        sta[t]=false;
        q.pop();

        for(int i=h[t];i!=-1;i=ne[i]){
            int u=e[i];

            if(dist[u]>dist[t]+w[i]){
                dist[u]=dist[t]+w[i];
                if(!sta[u]){
                    q.push(u);
                    sta[u]=true;
                }
            }

        }
    }
    if(dist[n]>0x3f3f3f3f/2) cout<<"impossible";
    else cout<<dist[n];


}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);

    }
    spfa();

    return 0;
}