这道题我又用的Ford。谁叫Ford好写啊。
出现负环就会一直重新更新一个节点，而一个点最多只会被更新(n-1)次，所以跑完(Ford)后，再看有没有节点可以更新即可。
代码：
#include <bits/stdc++.h>
using namespace std;
struct node{
int l , r , w;
};
node e[6010];
int n , m , tot;
int dis[2010];
void add(int x , int y , int z){
e[++tot].l = x;
e[tot].r = y;
e[tot].w = z;
}
int main(){
int T;
cin >> T;
while(T--){
cin >> n >> m;
tot = 0;
for(int i = 1; i <= m; i++){
int x , y , z;
cin >> x >> y >> z;
add(x , y , z);
if(z >= 0) add(y , x , z);
}
int ff = 0;
for(int i = 1; i <= tot; i++)
if(e[i].l == 1 || e[i].r == 1) ff = 1;
if(!ff){
cout << "NO" << endl;
continue;
}
memset(dis , 127 , sizeof(dis));
dis[1] = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j <= tot; j++)
dis[e[j].r] = min(dis[e[j].r] , dis[e[j].l] + e[j].w);
int f = 0;
for(int j = 1; j <= tot; j++)
if(dis[e[j].r] > dis[e[j].l] + e[j].w){
f = 1;
break;
}
if(!f) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}