思路

最短路径树知道吧，就是在图中经过所有点且代价最小的树。

最短路径树有一个特点，那就是总节点数刚好是 $n$。

那么如果最短路径树的总节点数大于 $n$，那么就出现负环了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20005,M = 60005,INF = 0x3fffffff;

// 链式前向星
struct edge{
	int u,v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {u,v,w,tail[u]};
	tail[u] = tot;
}

int dis[N],n,m;
bool f[N];
int cnt[N];
void bf(){
	queue<int> q;
	q.push(1);
	f[1] = 1;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		f[u] = 0;
		for (int j = tail[u];j;j = edges[j].prev){
			int v = edges[j].v,w = edges[j].w;
			if (dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				cnt[v] = cnt[u] + 1;	// 最短树上又多了一位新成员
				// 如果最短树上有重复的点，那么就有负环了
				if (cnt[v] > n){
					printf("YES\n");	// 有负环
					return;
				}
				if (!f[v])	q.push(v),f[v] = 1;
			}
		}
	}
	printf("NO\n");	// 没有负环
}
int main(int argc, char **argv){
	int t;
	cin >> t;
	while (t--){
		// 初始化
		fill(dis,dis + N,INF);
		memset(f,0,sizeof(f));
		memset(cnt,0,sizeof(cnt));
		memset(tail,0,sizeof(tail));
		tot = 0;

		cin >> n >> m;
		dis[1] = 0;
		cnt[1] = 1;
		for (int i = 0;i < m;i++){
			int u,v,w;
			cin >> u >> v >> w;
			add_edge(u,v,w);
			if (w >= 0)	add_edge(v,u,w);
		}
		bf();
	}
	return 0;
}