SPFA判断负环

liyuan2023 · 2025-04-13 14:18:09 · 个人记录

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5,inf=1e9;
int t,n,m,dis[N],cnt[N];
bool vis[N];
struct node{
    int v,w;
};
vector<node> g[N];
bool spfa(){
    queue<int> q;
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    cnt[1]=0;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto e:g[u]){
            int v=e.v,w=e.w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n){
                    return true;//存在负环
                }
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return false;//不存在负环
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        dis[1]=0;
        fill(dis+2,dis+n+1,inf);
        for(int i=1;i<=n;i++){
            g[i].clear();
        }
        for (int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            g[u].push_back({v,w});
            if(w>=0){
                g[v].push_back({u,w});
            }
        }
        bool flag=spfa();
        if(flag){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}