AcWing 904 虫洞

题目传送门

\(SPFA\)判断负环的祼题，模板题

#include 
using namespace std;
const int N = 510, M = 5210;
int n, m1, m2;
int dist[N]; // dist[x]记录源点到x的最短距离
int cnt[N];  // cnt[x]记录源点到x在产生最短距离时的边数
bool st[N];
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa() {
    /*注意：这句话在判断是不是负环时，写不写都是可以AC的
    为什么呢？原因很简单，因为就算是都是0，如果有负环，肯定在负环处会一次次进入
    队列,直到cnt[x]>=n,也是一样可以得到正确答案的，但为了代码的标准与一致性，
    还是要求写上 memset(dist,0x3f,sizeof dist);
    */
    //初始化距离INF
    memset(dist, 0x3f, sizeof dist);
    //是不是已经加入到集合中
    memset(st, 0, sizeof st);
    //初始化从源点到x的最短距离时，边数都是0
    memset(cnt, 0, sizeof cnt);

    queue q;
    //底层相当于有一个虚拟源点0
    // 0到 [1,n]的所有点，边权为0，不影响现在的图
    // 从虚拟节点0出发，到达所有的1~n，就成为了单源最短路径问题
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }
    // spfa
    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];
                /*
                dist[j]表示j点距离源点的距离，cnt[j]表示从源点到j点经过的边数
                cnt[j] = cnt[t] + 1 的意思是 如果距离更新了，那么从源点到j的边数就等于源点到t的边数
                + t到x的边数（即一条边）
                所以通过这个我们可以判断是否存在负环，如果在j，t之间存在负环，那么cnt[j] 会不断加1，
                我们通过判断如果cnt[j] >= n  进而确定是否存在负环。
                为什么是cnt[j] >= n ？ 因为cnt数组表示的是边数，如果从源点到j点的边数大于等于n，那么
                在源点和j点之间肯定存在n+1个点，但是最多只有n个点，根据抽屉原理，所以必然有点重复出现，
                存在负环 ！
                */
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n) return true;

                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m1 >> m2;
        //初始化邻接表
        memset(h, -1, sizeof h);
        idx = 0;
        int a, b, c;
        //田地 双向边
        while (m1--) {
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        //虫洞 回到t秒前 单向负边
        while (m2--) {
            cin >> a >> b >> c;
            add(a, b, -c);
        }
        //用spfa判断是不是有负环
        if (spfa())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}