一般的做法是bfsSPFA判断一下入队次数是否大于n次。
一个更好的想法是,用dfs版本的SPFA,判断存在一点在一条路径上出现多次。
把距离数组初始化为0,这样初始化后第一次只会加负边权松弛,枚举每个点为起点,找到一个负环就停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x) {
vis[x] = true;
for (auto pii : g[x]) {
int v = pii.first;
int d = pii.second;
if (dist[v] > dist[x] + d) {
dist[v] = dist[x] + d;
if (vis[v]) {
flag = true;
return;
}
dfs(v);
}
}
vis[x] = false;
}