#include<bits/stdc++.h>
#define MAXN 1005
#define inf INT_MAX
#define eps 1e-6
using namespace std;
struct Edge
{
    int v;
	double p;
    double w;
};
vector<Edge> e[MAXN],orig[MAXN];
double dis[MAXN];
bool vis[MAXN];
int cnt[MAXN],n,m,f[MAXN];
bool spfa(int s) 
{
    queue<int> q;
    fill(dis,dis+MAXN,inf);
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty()) 
	{
        int u=q.front(); q.pop();
        vis[u]=0;
        for(auto ed:e[u]) 
		{
            int v=ed.v;
            double w=ed.w;
            if(dis[v]>dis[u]+w) 
			{
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) return true;
                if(!vis[v]) 
				{
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return false;
}
bool check(double mid) 
{
    for(int i=1;i<=n;i++) 
	{
        e[i].clear();
        for(auto ed:orig[i]) 
		{
            e[i].push_back({ed.v,ed.p,mid*ed.p-f[ed.v]});
        }
    }
    return spfa(1); 
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1;i<=m;i++) 
	{
        int x,y,z;
        cin>>x>>y>>z;
        orig[x].push_back({y,z,0});
    }
    double l=0,r=10005,ans=0;
    while(r-l>eps) 
	{
        double mid=(l+r)/2;
        if(check(mid)) 
		{
            ans=mid;
            l=mid;
        } 
		else 
		{
            r=mid;
        }
    }
    printf("%.2lf",ans);
}

我下载了错的数据点：

输入：

6 6
1
1
1
100
100
100
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1

正确： 100.00

My Code: 1.00