简单做一下解释和注释

仅用于学习的笔记，有助于理解不太好理解的地方！

• 说明dist数组不进行初始化为0x3f3f3f3f的原因

参考代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
const int N = 2010, M = 10010;
int n, m, e[M], h[N], ne[M], idx, w[M];
// dist：这里不一定是起点到当前点的最短路径，没有具体意义
// cnt：表示从某个起点到当前点的最短路径的边数
int dist[N], cnt[N];
bool vis[N];

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool spfa(){
    queue<int> q;
    // 由于spfa更新的是队列中的邻边，1号点开始的路径不一定和负环联通，所以为了走到负环，将其全部加入队列
    for(int i = 1; i <= n; i++){
        q.push(i);
        vis[i] = true;
    }
    // 没有进行dist数组初始化为0x3f3f3f3f，因为当前dist数组并不存储最短路径了，任何值都可，只要比存在负环造成的负无穷大要大即可，所以0就满足情况，使用默认值即可
    while(q.size()){
        int t = q.front();
        q.pop();
        vis[t] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            // 队列初始时将所有点都加入队列，所以负环一定会发生更新并且一定会发生死循环到达边数为n然后返回true
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                // 路径个数大于等于n，有n个点，n - 1 条边，所以多出来的一条边一定会形成环，由于发生了更新，所以一定是负环（负环才可以将当前距离更新为更小值）
                if(cnt[j] >= n) return true;
                if(!vis[j]){
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if(spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}