洛谷P3385负环

传送门

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define re register

using namespace std;

const int maxn = 2005;

const int maxm = 3005;

inline int read(){

	char ch = getchar();

	int f = 1 , x = 0 ;

	while(ch > '9' || ch < '0') {if(ch == '-' ) f = -1 ; ch = getchar();}

	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0' ;ch = getchar();}

	return x * f;

}

int T,n,m,u,v,w;

int head[maxn],tot;

bool flag;

struct Edge{

	int from , to , next , val;

}edge[maxm << 1];

inline void add(int u , int v , int w){

	edge[++tot].from = u ;

	edge[tot].to = v;

	edge[tot].val = w;

	edge[tot].next = head[u];

	head[u] = tot;

}

int dis[maxn],num[maxn];

bool vis[maxn];

inline bool spfa(int s){

	for(re int i = 1 ; i <= n ; ++i)  dis[i] = 1e9 ;

	queue<int> q;

	q.push(s);

	dis[s] = 0;

	num[s]++;

	vis[s] = true;

	while(!q.empty()){

		int cur = q.front();

		q.pop(); vis[cur] = 0;

		for(re int i = head[cur] ; i ; i = edge[i].next) {

			int v = edge[i].to ;

			if(dis[v] > dis[cur] + edge[i].val) {

				dis[v] = dis[cur] + edge[i].val;

				if(!vis[v]) {

					q.push(v);

					num[v]++;

					vis[v] = true;

					if(num[v] > n)  return false;

				}

			}

		}

	}

	return true;

}

int main(){

	T = read();

	while(T--){

		memset(dis , 0 , sizeof(dis));

		memset(edge , 0 ,sizeof(edge));

		memset(num , 0 , sizeof(num));

		memset(head , 0 , sizeof(head));

		memset(vis , 0 , sizeof(vis));

		tot = 0;

		flag = 0;

		n = read(); m = read();

		for(re int i = 1 ; i <= m ; ++i){

			u = read(); v = read(); w = read();

			if(w < 0) add(u , v , w);

			else {

				add(u , v , w);

				add(v , u , w);

			}

		}

		if(spfa(1)) printf("N0\n");

		else printf("YE5\n");

	}

	return 0;

}