只能说我被一个小错搞得好心痛，本一写好代码感觉写的还优美，但一个小的不能再小的 i 写出u ,害的我正正调了一天。还不的不与别人对比看。OMG！！
具体的分析找别人的吧，说的比我好，要吃个苹果放松下
#include#include #include #include #include #define maxn 1005using namespace std;const int INF = 0x3f3f3f;double mid;struct Edge{ int from,to; int fun,cost; double dis; int next; void assign(int a,int b,int c,int d,int e){ from = a; to = b; cost = c; fun = d; next = e; //printf("%d %d %d %d \n",from,to,cost,fun); } void update(double k){ dis = -(fun - k * cost); } /* void print(){ printf("%d %d %d %d %.2lf\n",from,to,cost,fun,dis); }*/ }edge[5*maxn]; int F[maxn];int n,m;int head[maxn];int pv = 1;void Addedge(int a,int b,int c,int d){ int e = head[a]; head[a] = pv; edge[pv++].assign(a,b,c,d,e);}bool SPFA(){ int cnt[maxn]; bool inq[maxn]; double d[maxn]; memset(cnt,0,sizeof(cnt)); memset(inq,0,sizeof(inq)); for(int i=1;i<=n;i++) d[i] = INF; queue Q; while(!Q.empty()) Q.pop(); Q.push(1); inq[1] = true; d[1] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = false; for(int i=head[u];i != -1;i=edge[i].next){ int v = edge[i].to; if(d[v] > d[u] + edge[i].dis){ d[v] = d[u] + edge[i].dis; if(!inq[v]){ Q.push(v); inq[v] = true; if(++cnt[v] >= n) return true; } } } } return false;}int main(){ //if(freopen("input.txt","r",stdin)== NULL) {printf("Error\n"); exit(0);} //if(freopen("output1.txt","w",stdout)== NULL) {printf("Error\n"); exit(0);} cin>>n>>m; for(int i=1;i<=n;i++) cin>>F[i]; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int a,b,c,d; cin>>a>>b>>c; d = F[b]; Addedge(a,b,c,d); } double R=10000.0,L=0.0,ans = -1; while((R-L) > 1e-5){ mid = (R + L)/2; for(int i=1;i<=m;i++){ edge[i].update(mid); //edge[i].print(); } if(SPFA()) { ans = mid; L = mid; } else R = mid; } if(ans <= 0 ) printf("0\n"); else printf("%.2lf\n",L);}