思路：以val[u]-ans*edge[i].len最为边权，判断是否有正环存在，若有，那么就是ans小了。否则就是大了。
在spfa判环时，先将所有点进队列。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #include<cmath> #define Maxn 1010 #define Maxm 6000 #define inf 1e10 #define eps 1e-4 using namespace std; int vi[Maxn]; struct Edge{ int u,v,next; double len; }edge[Maxm]; double dis[Maxn],val[Maxn]; int head[Maxn],e,n,cnt[Maxn]; void add(int u,int v,double len) { edge[e].u=u,edge[e].v=v,edge[e].len=len,edge[e].next=head[u],head[u]=e++; } void init() { e=0; memset(vi,0,sizeof(vi)); memset(cnt,0,sizeof(cnt)); memset(head,-1,sizeof(head)); } int spfa(double ans) { int i,j,v,u; queue<int> q; memset(cnt,0,sizeof(cnt)); for(i=1;i<=n;i++){ dis[i]=0; q.push(i); vi[i]=1; } while(!q.empty()){ int u=q.front(); cnt[u]++; q.pop(); vi[u]=0; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; double d=val[u]-ans*edge[i].len; if(dis[v]<dis[u]+d){ dis[v]=dis[u]+d; cnt[v]++; if(cnt[v]>=n) return 1; if(!vi[v]){ q.push(v); vi[v]=1; } } } } return 0; } int main() { int i,j,a,b,m; double c; while(scanf("%d%d",&n,&m)!=EOF){ init(); for(i=1;i<=n;i++) scanf("%lf",val+i); for(i=1;i<=m;i++){ scanf("%d%d%lf",&a,&b,&c); add(a,b,c); } double l=0,r=2000,mid; while(r-l>eps){ mid=(l+r)/2; if(spfa(mid)) l=mid; else r=mid; } printf("%.2lf ",l); } return 0; }