SCU 1095运送物资(最短路)

X国发生了内战。起义军得到了广大人民的支持。在一次战役中，反动军队结集了大量兵力，围攻起义军的主堡W城。为支援前线，后方各个供给基地城市纷纷准备将物资运往W城。各基地及W城之间有的有公路相连。这就是说，有的基地不能将物资一次运到W城，必须通过中途的转运。

根据每条公路的长短和运送物资的多少，运送中将会有不同程度的损耗。现假设每条公路都有一个损耗系数，表示经过这条公路的物资总量与消耗量的比值。

另外，为保证物资安全到达，每个基地都会等所有要通过该基地转运的物资到齐后，连同本基地的物资一起，运到下一站。也就是说，从任何一个基地出发，都只能将物资运往另一基地，但允许多个基地的物资运往同一基地。

请编程预定出每个基地的运输路线，使到达W城的总物资最大。

输入：｛input.txt｝

第一行给出两个整数n(2<=n<=100)与m。其中n表示有n-1个基地（编号为1到n）与一个W城(编号为n)；m表示有m条公路。

第二行给出了n-1个正整数（正整数<=50000）,表示编号为1到n-1的基地要运送的物资数量。

接下来m行描述了m条公路的情况，每一行有3个数，如　1 2 0.1

表示1号城市与2号城市之间有一条公路连接，其损耗系数为0.1。

注意：数据给出的公路网，保证每个基地都能将物资运到W城。

输出：｛ouput.txt｝

共n行。

第一行是运到W城的最大物资数(结果保留两位小数)。

接下来n-1行分别有一个数，代表每个基地将物资运往的下一个基地或W城的编号。

样例输入

5 6

10 10 10 10

1 3 0

1 4 0

2 3 0

2 4 0

3 5 0

4 5 0

样例输出

40.00

解题报告

裸的最短路,在将边的权值表示为(1-损耗)的倒数。因为精度问题，倒数要开long double，并除以100,在计算路径时不是加而是乘。

#include<bits/stdc++.h>

#include<queue>

#include <algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#define Pair pair<long double,int>

#define MAXN 1000+10

#define MAXM 600000+1

using namespace std;

int n,m,num,head[MAXN],s,t,pre[MAXN],v[MAXM];

double good[MAXN],ans;

long double dis[MAXN];

struct Edge{

    int next,to,exi,from;

    double dis;

}edge[MAXM];

void add(int from,int to,double dis)

{

    edge[++num].next=head[from];

    edge[num].to=to;

    edge[num].dis=dis;

    edge[num].from=from;

    head[from]=num;

}

void dij()

{

    memset(dis,,sizeof(dis));

    memset(pre,,sizeof(pre));

    memset(v,,sizeof(v));

    priority_queue<Pair,vector<Pair>,greater<Pair> > h;

    for(int i=;i<=n;i++) dis[i]=LONG_LONG_MAX;

    dis[s]=*0.001;

    h.push(Pair(dis[s],s));

    while(h.size()>)

    {

        int k=h.top().second;h.pop();

        if(v[k]) continue;

        v[k]=;

        for(int i=head[k];i;i=edge[i].next)

        {

            if(((dis[k]*edge[i].dis))<(dis[edge[i].to]))

            {

                dis[edge[i].to]=dis[k]*edge[i].dis;

                pre[edge[i].to]=edge[i].from;

                h.push(Pair(dis[edge[i].to],edge[i].to));

            }

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

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

        scanf("%lf",&good[i]);

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

    {

        int x,y;double z;

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

        add(x,y,/(-z));

        add(y,x,/(-z));

    }

    s=n;

    dij();

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

         ans+=good[i]*(0.001/dis[i]);

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

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

    {

        printf("%d\n",pre[i]);

    }

    return ;

}