用SPFA判断负权图

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
#define ll long long
int e[N], ne[N], h[N], w[N], d[N], cnt[N], idx = 1;
int n, m;
bool st[N]; // 记录是否在队列里
void add (int a, int b, int c) {
　　e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa() {

/*关于为什么用SPFA判断负权图时不用初始化d数组到无穷大的理解：

1. 构造一个虚拟节点 O，单向指向所有的节点，且到所有节点距离为0；（也就是超级源点， 之前也做过一道用超级源点的图论题，，，在哪来着。。。。）
2. 新图是否有负环等价于原始的图。
3.dist数组一开始为0,没有违背算法过程，可以理解为根据算法已经从O 更新到了各个节点，接下来的代码就是顺理成章。所以dist数组从所有为0的状态开始是有对应意义的。就是先走一步。
*/
　　queue <int> q;
　　for (int i = 1; i <= n; ++ i) q.push(i), st[i] = 1;
　　while (!q.empty()) {
　　　　int t = q.front(); q.pop();
　　　　st[t] = 0;
　　　　for (int i = h[t]; i; i = ne[i]) {
　　　　　　int j = e[i];
　　　　　　if (d[j] > d[t] + w[i]) {
　　　　　　　　d[j] = d[t] + w[i];
　　　　　　　　cnt[j] = cnt[t] + 1;
　　　　　　　　if (cnt[j] >= n) return 1;
　　　　　　　　if (!st[j]) {
　　　　　　　　　　q.push(j);
　　　　　　　　　　st[j] = 1;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
　　return 0;
}
int main(){
　　ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
　　cin >> n >> m;
　　while (m -- ) {
　　　　int a, b, c;
　　　　cin >> a >> b >> c;
　　　　add(a, b, c);
　　}
　　int ans = spfa();
　　if (spfa()) cout << "Yes";
　　else cout << "No";
　　return 0;
}