题目链接：https://www.luogu.com.cn/problem/P3385
解题思路：完全参考自 MoonSkyy大佬的博文
核心思想：
\(cnt_u\) 表示起点到 \(u\) 的最短路所经过边数，如果 \(cnt_u \ge n\) 则说明路径至少包含 \(n\) 条边 \(n+1\) 个点，必然存在负环。
示例程序：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
struct Edge { int v, w; };
vector<Edge> g[maxn];
int T, n, m;
// SPFA
int dis[maxn];
int cnt[maxn];
bool ins[maxn]; // 判断是否在队列中
bool spfa() {
stack<int> stk;
memset(dis, 0x3f, sizeof(int)*(n+1));
memset(cnt, 0, sizeof(int)*(n+1));
memset(ins, 0, sizeof(bool)*(n+1));
dis[1] = 0;
stk.push(1);
while (!stk.empty()) {
int u = stk.top();
stk.pop();
ins[u] = false;
for (auto e : g[u]) {
int v = e.v, w = e.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n)
return true;
if (!ins[v])
ins[v] = true, stk.push(v);
}
}
}
return false;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
if (w >= 0)
g[v].push_back({u, w});
}
puts(spfa() ? "YES" : "NO");
}
return 0;
}