博客

7-1 城市间紧急救援 （25 分）

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

一道典型的最短路径问题，首先想到使用迪杰斯特拉算法，进行最短路i经的求解，

迪杰斯特拉算法详解

。

但是当我们深入分析时却发现，自己没有办法统计最短路径的条数和能够召集的最多的救援队数量，我们只能统计最短路径的边权值。

在翻博客的时候看到了大佬说的一句话：

一切算法皆思想

，掌握了算法思想就掌握了这一类所有算法，然后再看大佬的代码，真的是将思想掌握的很透彻，和板子完全不同，但又思想一致，功能相同，在此ORZ一波，希望自己也能达到那种水平。

言归正传，在进行算法时，我们是不统计如果长度相同时的情况的，但是最短路径的条数和能够召集的最多的救援队数量的求取都都要求我们对这类情况进行讨论，能够召集的最多的救援队数量就可以在这里进行求解。

有人可能会这么想最短路径的条数是不是只要最短路径相等，而且到达的点为终点，就设立一个变量使它+1呢？

首先这个是错误的，因为每个点都有多条路径到达，而

到达最终定点的路径的个数等于各个点的路径的乘积

，这是我们需要特别注意的地方，那么剩下的就是代码实现了。

下面给出AC代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn=500+10;
const int INF=0x3f3f3f3f;
int V,E,s,t,num=0;
int cost[maxn][maxn];
int d[maxn];
int prev1[maxn];
int value[maxn];
int roadnum[maxn];
int amount[maxn];
bool used[maxn];



void dijkstra(int s)
{
    memset(d,INF,sizeof(d));
    memset(used,false,sizeof(used));
    memset(prev1,-1,sizeof(prev1));
    memset(roadnum,0,sizeof(roadnum));
    memset(amount,0,sizeof(amount));
    d[s]=0;
    roadnum[s]=1;
    amount[s]=value[s];

    while(true)
    {
        int v=-1;
        for(int u=0;u<V;u++)
        {
            if(!used[u]&&(v==-1||d[u]<d[v])) v=u;
        }

        if(v==-1) break;
        used[v]=true;

        for(int u=0;u<V;u++)
        {

            if(d[u]>d[v]+cost[v][u])
            {
                d[u]=d[v]+cost[v][u];
                amount[u]=amount[v]+value[u];
                roadnum[u]=roadnum[v];
                prev1[u]=v;
                //cout<<"gg1:     "<<amount[u]<<"    "<<u<<"    "<<v<<endl;
            }
            else if(d[u]==d[v]+cost[v][u])
            {
                roadnum[u]+=roadnum[v];
                if(amount[u]<amount[v]+value[u])
                {
                    amount[u]=amount[v]+value[u];
                    prev1[u]=v;
                    //cout<<"gg2:     "<<amount[u]<<"    "<<u<<"    "<<v<<endl;

                }

            }

        }
    }
}


int main()
{
    scanf("%d %d %d %d",&V,&E,&s,&t);
    for(int i=0;i<V;i++) memset(cost[i],INF,sizeof(cost[i]));

    for(int i=0;i<V;i++) scanf("%d",&value[i]);
    for(int i=0;i<E;i++)
    {
        int a,b,c; scanf("%d %d %d",&a,&b,&c);
        cost[a][b]=cost[b][a]=c;
    }
    dijkstra(s);

    int prevt[maxn];
    int pos=0;

    int tt=t;
    for(;tt!=-1;tt=prev1[tt])
    {
        prevt[pos++]=tt;
    }

    printf("%d %d\n",roadnum[t],amount[t]);
    for(int i=pos-1;i>=0;i--)
    {
        if(i) printf("%d ",prevt[i]);
        else printf("%d",prevt[i]);
    }

    return 0;
}