zoj 1655 Transport Goods

#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<stdlib.h>using namespace std;#define MMV 105#define MME 100000int inf = 1000000000;struct edge_t{    int s, t;    double w;};edge_t arrEdge[MME];int szEdge;double dis[MMV];int nv, ne;int post[MMV];bool Bellman(int s){    int i, j;    for(i = 1;  i <= nv; i++)        dis[i] = -inf;    dis[s] = post[s];    for(i = 1; i < nv; i++)    {        for(j = 1; j <= szEdge; j++)        { edge_t e = arrEdge[j]; if(dis[e.t] < dis[e.s]*(1 - e.w))     dis[e.t] = dis[e.s]*(1 - e.w); if(dis[e.s] < dis[e.t]*(1 - e.w))     dis[e.s] = dis[e.t]*(1 - e.w);        }    }    return true;}int main(){    int i, j, s, t;    double w;    while(scanf("%d %d", &nv, ≠)==2)    {        memset(post, 0, sizeof(post));        for(i = 1; i < nv; i++) scanf("%d", &post[i]);        szEdge = 0;        for(i = 1; i <= ne; i++)        { scanf("%d %d %lf", &s, &t, &w); ++szEdge; arrEdge[szEdge].s = s; arrEdge[szEdge].t = t; arrEdge[szEdge].w = w;        }double sum = 0;        for(i = 1; i < nv; i++)        { if(Bellman(i))     if(dis[nv]>0)         sum += dis[nv];        }        printf("%.2lfn", sum);    }    return 0;}