12.spfa判断负环

spfa算法判断负环时间复杂度最坏nm
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 10010;
 4 int h[N], e[N], ne[N], idx, w[N];
 5 int dist[N], cnt[N];
 6 //dist数组存储每个点到1号点的最短路的距离
 7 //cnt数组存储这个最短路的边数
 8 bool st[N];
 9 int n, m;
10 void add(int a, int b, int c) {
11     e[idx] = b;
12     w[idx] = c;
13     ne[idx] = h[a];
14     h[a] = idx++;
15 }
16 bool spfa() {
17     memset(dist, 0x3f, sizeof dist);
18     dist[1] = 0;
19     queue<int> q;
20     for (int i = 1; i <= n; i++) { //把所有点放进队列
21         q.push(i);
22         st[i] = true;
23     }
24     while (q.size()) {
25         int t = q.front();
26         q.pop();
27         st[t] = false;
28         for (int i = h[t]; i != -1; i = ne[i]) {
29             int j = e[i];
30             if (dist[j] > dist[t] + w[i]) {
31                 dist[j] = dist[t] + w[i];
32                 cnt[j] = cnt[t] + 1;
33                 //从1到t的边数加上这一条边
34                 if (cnt[j] >= n) { //抽屉原理
35                     return true;
36                 }
37                 if (!st[j]) {
38                     q.push(j);
39                     st[j] = true;
40                 }
41             }
42         }
43     }
44     return false;
45 }
46 int main() {
47     memset(h, -1, sizeof h);
48     cin >> n >> m;
49     while (m--) {
50         int a, b, c;
51         cin >> a >> b >> c;
52         add(a, b, c);
53     }
54     if (spfa()) {
55         cout << "Yes" << endl;
56     } else {
57         cout << "No" <<endl;
58     }
59     return 0;
60 }