AcWing 852. spfa判断负环 边权可能为负数。

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

const int N = , M = ;

int n, m;

int h[N], w[M], e[M], ne[M], idx;

int dist[N];//最短距离

int cnt[N];//当前最短路的边数，如果大于等于n，那么有负环

bool st[N];

void add(int a, int b, int c) {

    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;

}

int spfa() {

    queue<int> q;

    for (int i = ; i <= n; i ++ ) {

        st[i] = true;//可能负环1到不了，那么就把所有的点加进去

        q.push(i);

    }

    while (q.size()) {

        int t = q.front();

        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -; i = ne[i]) {

            int j = e[i];

            if (dist[j] > dist[t] + w[i]) {

                dist[j] = dist[t] + w[i];

                cnt[j] = cnt[t] + ;

                if (cnt[j] >= n) return true;

                if (!st[j]) {

                    q.push(j);

                    st[j] = true;

                }

            }

        }

    }

    return false;

}

int main() {

    scanf("%d%d", &n, &m);

    memset(h, -, sizeof h);

    while (m -- ) {

        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);

        add(a, b, c);

    }

    if (spfa()) puts("Yes");

    else puts("No");

    return ;

}