POJ 3259

POJ 3259

SPFA 判负环

注意双向边，题目中的边要\(*2\)

输出的是\(YES\) 不是 \(Yes\)

给我整吐了，下次仔细看题。

题意

输入\(n\)个点，\(m\)条边，\(backt\)条负权边，判断这个图中是否有负环

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define endl '\n'
const int N = 5210;
int e[N],w[N],ne[N],h[N],idx,dist[N],cnt[N],n,m,backt;
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(){
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    memset(cnt,0,sizeof cnt);
    queue<int> q;
    dist[1] = 0;
    for(int i = 1;i <= n; ++i){
        q.push(i);
        st[i] = 1;
    }
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = 0;
        for(int i = h[t];i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[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);
    int t,a,b,c;
    cin >> t;
    while(t --) {
        memset(h,-1,sizeof h);
        idx = 0;
        cin >> n >> m >> backt;
        for(int i = 0;i < m; ++i) {
            cin >> a >> b >> c;
            add(a,b,c);
            add(b,a,c);
        }
        for(int i = 0;i < backt; ++i) {
            cin >> a >> b >> c;
            add(a,b,-c);
        }
        if(spfa()) cout << "YES" ;
        else cout << "NO" ;
        if(t) cout << endl;
    }
    return 0;
}

POJ 3259

原文：https://www.cnblogs.com/lukelmouse/p/12424177.html