L2-001 紧急救援（25 分）

我不是女神ヾ 2022-03-18 15:55 233阅读 0赞

### 题目描述： ###

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

输入格式:  
输入第一行给出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

###### 分析： ######

这个题一开始我没考虑周到，直接用了Floyd算法。测试数据后才发现根本不可以这样。于是改用dijkstra算法。  
因为这个题要输出有多少条最短路径，所以我们用一个cnt数组来保存S到各个点的最短路径条数。  
例如：cnt\[5\]就表示S到5的最短路径条数。  
这个题还要输出最多能携带多少个消防员，所以我们用一个nunber数组来保存S到各个点时能携带的最多人数。  
例如：nunber\[5\]表示S到5这个点最多能携带的人数。  
至于最后输出的经过城市的编号，我们直接用一个Ｐ数组保存每个城市的前驱就好了（模板里面也有这个数组，不过多复述）。  
我们还需要用一个num数组保存每个城市的消防员人数。  
例如num\[5\]表示编号为5的城市的消防员人数。  
那么具体实施的时候，谨记：我们如果碰到了最短路径相同的情况，就比较消防员人数的多少，来进行赋值。  
基本和模板差不多，但是在赋初值的时候需要注意。  
我因为赋值的问题wa了几个小时，内心绝望。  
具体操作见代码详解：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    #define INF 1000000
    int num[510];
    int number[510];
    int cnt[510];
    void Dijkstra(int Graph[][510],int P[510],int N,int S,int D)
    {
        int i,j,k,minx;
        int vis[510];//表示是否已经摆放过这个城市
        int weight[510];
        for(int i=0;i<N;i++)
        {
            number[i]=0;//初始化每个城市最多携带的人数为0
            vis[i]=0;//表为拜访
            P[i]=S;//初始化下标为i的城市编号的前驱为S。
        }
        //从vis[s]开始访问。S号城市最多能携带的人数为S城市有的人数即num[s].
        vis[S]=1;weight[S]=0;number[S]=num[S];cnt[S]=1;//cnt[s]=1 表到S有一条最短路径道路
        for(i=0; i<N; i++)//对weight初始化，其他数组相应初始化
        {
            weight[i]=Graph[S][i];
            if(Graph[S][i]!=INF&&i!=S)//如果此条件成立，那么表示S与i号城市之间有道路连接，则需改变其他数组的值
            {
                P[i]=S;//将i号城市的前驱改为S。
                number[i]=num[i]+num[S];//能到达i号城市的人数为S和i号城市的人数和。
                cnt[i]=1;//并且当前的最短路径只有一条
            }
        }
        for(i=1; i<N; i++)
        {
            minx=INF;
            j=0;
            k=-1;
            while(j<N)//找到最小的路径
            {
                if(vis[j]==0&&minx>weight[j])
                {
                    minx=weight[j];
                    k=j;
                }
                j++;
            }
            if(k==-1)//如果此条件成立，则表示没有找到最小的路径了。直接return
                return ;
            vis[k]=1;//标记为访问过的状态
            for(j=0; j<N; j++)//更新weight数组
            {
    
                if(!vis[j]&&Graph[k][j]!=INF)//表示k和j之间有道路连接，需要考虑更不更新weight[j]中的值
                {
                    if(weight[k]+Graph[k][j]<weight[j])//如果成立，则表示更短的路径
                    {
                        P[j]=k;//将j号城市的前驱改为k
                        cnt[j]=cnt[k];//到j号城市最短路径的条数也就是到k号城市的最短路径的条数
                        weight[j]=weight[k]+Graph[k][j];//更新
                        number[j]=num[j]+number[k];/*到j号城市能携带的最多的消防员数量为到
                        k号城市能携带的最多消防员数量加上j号城市本身的消防员数量。*/
                    }
                    /*看最短路径是否相同，如果成立则要比较最多人数*。
                    else if((weight[k]+Graph[k][j])==weight[j])
                    {//比较是通过k号城市到j城市人数多，还是通过之前那条最短路径的人数多。
                        if(num[j]+number[k]>number[j])//如成立，则要更新number[j]
                        {
                            number[j]=num[j]+number[k];//如果
                            P[j]=k;//要更新j号城市的前驱
                        }
                        cnt[j]+=cnt[k];/*只要路径长度相等，那么就要把到j号城市的最短路径数加上
                        到k号城市的最短路径就可以了/*
                  
                }
            }
        }
    }
    int Graph[510][510];
    int P[510];
    int main()
    {
        int N,M,S,D;
        while(~scanf("%d%d%d%d",&N,&M,&S,&D))
        {
            for(int i=0; i<N; i++)//初始化Graph数组
                for(int j=0; j<N; j++)
                {
                    if(i==j)//自己到自己，长度自然为0
                        Graph[i][j]=0;
                    else
                        Graph[i][j]=INF;
                }
            for(int i=0; i<N; i++)
                scanf("%d",&num[i]);//num记录每个城市的消防员人数
            for(int i=0; i<M; i++)//输入道路情况
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                    Graph[a][b]=c;
                    Graph[b][a]=c;
            }
            Dijkstra(Graph,P,N,S,D);
            int sum=0;
            int p[510];
            int k=0;
            int d=D;
            while(S!=D)
            {
                p[k++]=D;
                D=P[D];
            }
            p[k++]=S;
            printf("%d %d\n",cnt[d],number[d]);
            for(int i=k-1; i>0; i--)
                printf("%d ",p[i]);
            printf("%d\n",p[0]);
        }
    }