提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2010;
struct node {
	int v , w;
};
int t , n , m , flag;
vector <node> e[N];
int dis[N] , cnt[N] , vis[N];
queue <int> q;
bool spfa(int n, int s) {
  	memset(dis, 0x3f, (n + 1) * sizeof(int));
  	memset(vis, 0 , sizeof (vis));
  	memset(cnt, 0 , sizeof (cnt));
  	dis[s] = 0, vis[s] = 1;
  	q.push(s);
  	while (!q.empty()) {
	    int u = q.front();
	    q.pop(), vis[u] = 0;
	    for (auto ed : e[u]) {	
     	 	int v = ed.v, w = ed.w;
    	 	if (dis[v] > dis[u] + w) {
    	    	dis[v] = dis[u] + w;
    		    cnt[v] = cnt[u] + 1;  
     	   		if (cnt[v] >= n) return false;
     	   		if (!vis[v]) q.push(v), vis[v] = 1;
      		}
    	}
  	}
  return true;
}
signed main () {
	cin >> t;
	while (t --) {
		cin >> n >> m;
		flag = 1;
		while (m --) {
			int a , b , c;
			cin >> a >> b >> c;
			e[a].push_back ( node {b , c} ) ;
			if (c > 0)
			e[b].push_back ( node {a , c} ) ;
		}
		for (int i = 1;i <= n;i ++) {
			if ( !spfa (n , i) ) {
				cout << "YES\n";
				flag = 0;
				break;
			}
		}
		if ( flag ) cout << "NO\n";
	}
		
	return 0;
}