c++ Bellmanford

#include <bits/stdc++.h>
using namespace std;

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

const int N=1005;
const double EPS=1e-4;
int f[N]
double dist[N];
int n, m;

struct Edge{int x, y, w;};
vector<Edge> e;

bool bellmanford(double k){
    memset(dist, 0x00, sizeof dist);
    bool flag=true;
    for(int i=0; i<n-1; ++i){
        flag=true;
        for(int j=0; j<e.size(); ++j){
            int x=e[j].x, y=e[j].y, w=e[j].w;
            if(dist[y]<dist[x]+f[y]-k*w){
                dist[y]=dist[x]+f[y]-k*w;
                flag=false;
            }
        }
        if(flag) break;
    }

    // 正环检测
    for(int j=0; j<e.size(); ++j){
        int x=e[j].x, y=e[j].y, w=e[j].w;
        if(dist[y]<dist[x]+f[y]-k*w) return true;
    }
    return false;
}



int main(){
    memset(f, 0x00, sizeof f);
    cin>>n>>m;

    for(int i=1; i<=n; ++i) cin>>f[i];
    for(int i=0; i<m; ++i){
        int x, y, w;
        cin>>x>>y>>w;
        e.push_back({x, y, w});
    }

    double l=0, r=1005;
    while(l+EPS<r){
        double mid = l+(r-l)/2;
        if(bellmanford(mid)) l=mid;
        else r=mid;
    }

    cout<<fixed<<setprecision(2)<<l<<endl;

    return 0;
}

c++ SPFA

#include <bits/stdc++.h>
using namespace std;

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

const int N=1005;
const double EPS=1e-4;
int f[N], cnt[N];
bool vis[N];
double dist[N];
int n, m;
vector<PII> g[N];

// 使用正环判定
bool spfa(double k){
    memset(vis, 0x00, sizeof vis);
    memset(cnt, 0x00, sizeof cnt);
    memset(dist, 0x00, sizeof dist);

    queue<int> q;
    for(int i=1; i<=n; ++i){q.push(i); vis[i]=true;}
    while(!q.empty()){
        int node =q.front(); q.pop();
        vis[node]=false;
        for(PII &e: g[node]){
            int v=e.fi, w=e.se;
            if(dist[v]<dist[node]+f[node]-k*w){
                dist[v]=dist[node]+f[node]-k*w;
                cnt[v]=cnt[node]+1;
                if(cnt[v]==n) return true; // 找到正环
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    return false; // 当前k值下没有正环

}


int main(){
    memset(f, 0x00, sizeof f);
    cin>>n>>m;

    for(int i=1; i<=n; ++i) cin>>f[i];
    for(int i=0; i<m; ++i){
        int x, y, w;
        cin>>x>>y>>w;
        g[x].push_back({y, w});
    }

    double l=0, r=1005;
    while(l+EPS<r){
        double mid = l+(r-l)/2;
        if(spfa(mid)) l=mid;
        else r=mid;
    }

    cout<<fixed<<setprecision(2)<<l<<endl;

    return 0;
}