P3385 【模板】负环（SPFA）

题目链接:https://www.luogu.com.cn/problem/P3385

题解

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n;
int m;int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n>>m;vector<vector<pair<int,int>>>graph(n+1);vector<int>dis(n+1,INT_MAX);vector<bool>enter(n+1,false);queue<int>que;vector<int>update(n+1,0);for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;if(w>=0){graph[u].push_back({v,w});graph[v].push_back({u,w});}else{graph[u].push_back({v,w});}}dis[1]=0;que.push(1);enter[1]=true;update[1]=1;int cmd=0;while(!que.empty()){int x = que.front();enter[x]=false;que.pop();for(auto edge:graph[x]){int to = edge.first;int ww = edge.second;if(dis[to]>dis[x]+ww){dis[to]=dis[x]+ww;if(!enter[to]){update[to]++;que.push(to);enter[to]=true;                       }}  if(update[to]>=n){cmd=1;break;}}if(cmd==1)break;}if(cmd==1)cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}