spfa判断边权和为负的环——判断任一点松弛次数大于n
作者:
zhangas2
,
2024-03-15 21:29:14
,
所有人可见
,
阅读 14
#include<bits/stdc++.h>
#define endl '\n'
#define PII pair<int,int>
//#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;}
vector<PII> g[2005];
int cnt[2005];
int n, m;
int st[2005];
int dist[2005];
int spfa(int start){
queue<int> q;
q.push(start);
st[start] = 1;
memset(dist, 0x3f, sizeof(dist));
dist[start] = 0;
// 松弛次数
cnt[start] = 1;
while(q.size()){
int u = q.front(); q.pop();
st[u] = 0;
for(int i = 0; i < g[u].size(); ++ i){
int v = g[u][i].first, w = g[u][i].second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
if(!st[v]){
q.push(v);
st[v] = 1;
cnt[v] ++;
if(cnt[v] > n) return 1;
}
}
}
}
return 0;
}
void solve(){
n = read(), m = read();
for(int i = 0; i < m; ++ i){
int u = read(), v = read(), w = read();
g[u].push_back({v, w});
if(w >= 0) g[v].push_back({u, w});
}
if(spfa(1)) cout << "YES" << endl;
else cout << "NO" << endl;
for(int i = 1; i <= n; ++ i){
g[i].clear();
cnt[i] = st[i] = 0;
}
}
signed main(){
int _ = read();
while(_ --) solve();
return 0;
}