c++ Bellman-ford 判负环

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N=505, M=5205;
int T, n, m, w, K=0;
int dist[N];
struct Edge{int x, y, t;}e[M];

bool bellmanford(){ // 如果存在负环, 从任一点出发均可找到, 可以不用初始化
    bool flag=true;
    for(int i=0; i<n-1; ++i){
        flag=true;
        for(int j=0; j<K; ++j){
            if(dist[e[j].y]>dist[e[j].x]+e[j].t){
                dist[e[j].y]=dist[e[j].x]+e[j].t;
                flag=false;
            }
        }
        if(flag) break; // 当前无更新操作, 跳出
    }
    // 负环检测
    for(int j=0; j<K; ++j){
        if(dist[e[j].y]>dist[e[j].x]+e[j].t) return true;
    }
    return false;
}

int main(){
    // bellman-ford算法求负环
    scanf("%d", &T);
    while(T--){
        memset(dist, 0x3f, sizeof dist);
        scanf("%d%d%d", &n, &m, &w);
        // 读入双向边
        int x, y, t;
        K=0;
        for(int i=0; i<m; ++i){
            scanf("%d%d%d", &x, &y, &t);
            e[K].x=e[K+1].y=x;
            e[K].y=e[K+1].x=y;
            e[K].t=e[K+1].t=t;
            K+=2;
        }

        // 读入warmholes
        for(int i=0; i<w; ++i){
            scanf("%d%d%d", &x, &y, &t);
            e[K].x=x;
            e[K].y=y;
            e[K++].t=-t;
        }
        if(bellmanford()) printf("%s\n", "YES");
        else printf("%s\n", "NO");
    }

    return 0;
}

c++ SPFA判负环

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

using namespace std;

typedef pair<int, int> PII;
#define fi first
#define se second

const int N=505;
int T, n, m, w;
int dist[N], vis[N], f[N]; // f[N]记录每个点出队的次数

vector<PII> g[N];

bool SPFA(){
    queue<PII> q;
    for(int i=1; i<=n; ++i){
        q.push({dist[i], i});
        vis[i]=true;
    }

    while(!q.empty()){
        int node=q.front().se;
        // f[node]++;
        // if(f[node]>=n) return true;
        q.pop();
        vis[node]=false;
        for(auto &e: g[node]){
            int v=e.fi;
            int w=e.se;
            if(dist[v]>dist[node]+w){
                dist[v]=dist[node]+w;
                q.push({dist[v], v});
                f[v]=f[node]+1;
                if(f[v]==n) return true;
                vis[v]=true;
            }
        }
    }
    return false;
}

void init(){
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0x00, sizeof vis);
    memset(f, 0x00, sizeof f);
    for(int i=1; i<=N; ++i) g[i].clear();
}


int main(){
    // spfa算法求负环
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &m, &w);
        init();
        // 读入双向边
        int x, y, t;
        for(int i=0; i<m; ++i){
            scanf("%d%d%d", &x, &y, &t);
            g[x].push_back({y, t});
            g[y].push_back({x, t});
        }

        // 读入warmholes
        for(int i=0; i<w; ++i){
            scanf("%d%d%d", &x, &y, &t);
            g[x].push_back({y, -t});
        }
        if(SPFA()) printf("%s\n", "YES");
        else printf("%s\n", "NO");
    }

    return 0;
}