AcWing 851. spfa求最短路&&AcWing 852. spfa判断负环—spfa算法

问题链接:AcWing 851. spfa求最短路
问题描述

spfa算法是对bellman-ford算法的改进，bellman-ford算法比较笨，要遍历所有边来更新，其实如果当前点没有被更新的话，就不用用当前点来更新他所连接的点了。我们只需要每次更新一个点后，继续更新该点连接的点即可。
代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e5+10,INF=0x3f3f3f3f;

struct E{
    int v,w,nxt;
};
E edge[M];
int head[N], idx=0;
int n,m;
int dist[N];
int st[N];

void init(){
    for(int i=0;i<=n;i++){
        head[i]=-1;
        dist[i]=INF;
    }
}
void add(int u,int v,int w){
    edge[idx].v=v;
    edge[idx].w=w;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}
int spfa(){
    dist[1]=0;
    st[1]=1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=head[t];~i;i=edge[i].nxt){
            int v=edge[i].v;
            int w=edge[i].w;
            if(dist[v]>dist[t]+w){
                dist[v]=dist[t]+w;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return dist[n];
}
int main(){
    cin>>n>>m;
    init();
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    int k=spfa();
    if(k<INF/2) cout<<k;
    else puts("impossible");
    return 0;
}

我这里用的是链式前向星来存图
问题链接:AcWing 852. spfa判断负环
问题描述

正如bellman-ford算法中提到的，一个点到其余点的最短路径，最长需要经过n-1条边，所以如果有大于等于n条边，则说明一定有环。注意从单元点出发，有可能找不到环，因为环不一定在最短路径上。
代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e5+10,INF=0x3f3f3f3f;

struct E{
    int v,w,nxt;
};
E edge[M];
int head[N], idx=0;
int n,m;
int dist[N];
int st[N];
int cnt[N];

void init(){
    for(int i=0;i<=n;i++){
        head[i]=-1;
        dist[i]=INF;
    }
}
void add(int u,int v,int w){
    edge[idx].v=v;
    edge[idx].w=w;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}
bool spfa(){
    dist[1]=0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    } 
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=head[t];~i;i=edge[i].nxt){
            int v=edge[i].v;
            int w=edge[i].w;
            if(dist[v]>dist[t]+w){
                cnt[v]=cnt[t]+1;
                if(cnt[v]>=n) return false;
                dist[v]=dist[t]+w;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return true;
}
int main(){
    cin>>n>>m;
    init();
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    int k=spfa();
    if(!k) puts("Yes");
    else puts("No");
    return 0;
}