zoj1665 dij变形

既然输入的是损坏率，那1-x就是剩余的。最后只要剩余的最大。

#include<stdio.h>

#include<string.h>

#define Max 99999999

const int maxn=;

double dis[maxn],map[maxn][maxn];

int vis[maxn],n,val[maxn];

void init()

{

    int i,j;

    for(i=;i<=n;i++)

        for(j=;j<=n;j++)

            if(i==j)

                map[i][j]=;

            else map[i][j]=;

}

void dij()

{

    int i,j,pos;

    pos=n;

    memset(vis,,sizeof(vis));

    for(i=;i<=n;i++)

        dis[i]=;

    dis[pos]=;

//    vis[pos]=1;

    for(i=;i<=n;i++)

    {

        double min=-Max;

        for(j=;j<=n;j++)

        {

            if(!vis[j]&&min<dis[j])

            {

                pos=j;

                min=dis[j];

            }

        }

        vis[pos]=;

        for(j=;j<=n;j++)

        {

            if(!vis[j]&&dis[j]<map[pos][j]*dis[pos])

                dis[j]=map[pos][j]*dis[pos];

        }

    }

}

int main()

{

    int i,j,m;

    double cost;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        init();

        for(i=;i<n;i++)

            scanf("%d",&val[i]);

        for(i=;i<=m;i++)

        {

            int x,y;

            scanf("%d%d%lf",&x,&y,&cost);

            if(map[x][y]<-cost)

                map[x][y]=map[y][x]=-cost;

        }

        /*for(i=1;i<=n;i++)

        {

            for(j=1;j<=n;j++)

            {

                printf("%.2lf ",map[i][j]);

            }

            printf("\n");

        }*/

        double ans=;

        dij();

        /*for(i=1;i<=n;i++)

            printf("%d ",dis[i]);

        printf("\n");*/

        for(i=;i<n;i++)

            ans+=val[i]*dis[i];

        printf("%.2lf\n",ans);

    }

}