SPFA判负环

模板库

地址

深搜版 $SPFA$ ：如果更新 $dis$ 的时候两次经过一个点，那么一定有负环

#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 200000+9;
const int MAXM = 200000+9;
struct E{
    int next,to;
    int val;
}edge[MAXM<<1];
int head[MAXN],edge_num;
int n,m;
bool pd;
bitset<MAXN> vis;
int dis[MAXN];
void addedge(int x,int y,int v){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    edge[edge_num].val=v;
    head[x]=edge_num;
}
void SPFA(int x){
    if(pd)return;
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        if(pd)return;
        if(dis[x]+edge[i].val<dis[edge[i].to]){
            dis[edge[i].to]=dis[x]+edge[i].val;
            if(vis[edge[i].to]){
                pd=1;
                return;
            }
            SPFA(edge[i].to);
        }
    }
    vis[x]=0;
}
void solve(){
    for(int i=1;i<=n;i++){
        SPFA(i);
        if(pd){puts("YE5");return;}
    }
    puts("N0");
}
int main(){
    int kase;
    scanf("%d",&kase);
    while(kase--){
        memset(head,0,sizeof(head));
        vis.reset();
        memset(dis,0,sizeof(dis));
        edge_num=0;
        pd=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            if(c>=0)addedge(b,a,c);
        }
        solve();
    }
    return 0;
}