#include <bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int M=6e3+10;
int E,V;
int d[N];
struct edge{
int from;
int to;
int cost;
}es[M],t[M/2];
bool find_negative_loop() {
memset(d,0,sizeof d);
for(int i=0;i<V;i++) {
for(int j=0;j<E;j++) {
edge e=es[j];
if(d[e.to]>d[e.from]+e.cost) {
d[e.to]=d[e.from]+e.cost;
if(i==V-1) return true;
}
}
}
return false;
}
int main() {
int T;
cin>>T;
while(T--) {
cin>>V>>E;
int k=0;
for(int i=0;i<E;i++) {
cin>>es[i].from>>es[i].to>>es[i].cost;
es[i].from--;es[i].to--;
if(es[i].cost>=0) {
t[k].from=es[i].to;
t[k].to=es[i].from;
t[k].cost=es[i].cost;
k++;
}
}
for(int i=E;i<E+k;i++) {
es[i]=t[i-E];
}
E+=k;
if(!find_negative_loop()) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
就对了一个点,求助各位大佬!