PTA-GPLT L2-001 紧急救援 （Dijkstra）

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840

L2-001 紧急救援 （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

---

题目大意：知道各个城市和各个城市之间的距离，求起点到终点的最短路径的条数和最多的救援队数量，并输出最优路径。

这里路径长度相当于距离的权，每个城市救援队的数量相当于点的权。最短路径是指距离最短，最优路径是指在最短路径中，找一个救援队数量最多的路径（如果最短路径只有一个了话，最优路径当然就只能是它）。题目中说了保证最优路径只有一个，也就是最短路径可能有很多，但是他们的救援队数量最多的只有一个。

 

一开始是用优先队列来写的，还把输出最短路径的条数理解错了，以为是最短路径上的线段数量，就是城市数减去1嘛。提交后竟然测试用例1和3过了，2是错误，4是超时。过了的两个应该纯属是数设置的太巧了，测试4超时说明BFS对于加权路径还是不适用。

 

大二上数据结构讲了Kruskal算法和Prim算法，求加权连通图的最小生成树。当时只是会用笔和纸画画就行，并没有在电脑上实现。Dijkstra算法和Prim算法很相似，类似于在求最小生成树的同时也得到了单源最短路径。老师上课讲的时候也认真听了，感觉很好理解，但是现在复习再看，只有文字和图片，确实没有别人直接给你讲来的直观。网上讲的也很多，这里贴一个个人认为写的好的。https://blog.csdn.net/tianhaobing/article/details/65443049

代码参考的这一篇：https://blog.csdn.net/HowardEmily/article/details/56681947

 

a记录地图，vis记录城市是否在最小生成树上，dis记录各点到起点的最小距离。path记录到达该城市的上一个城市，用来从终点回溯到起点，path_num记录最短路径的条数（就是到达某个城市的最短路径可能不止一个，但是他们长度都是最短的），sum记录救援队的总数，w记录城市原有救援队的数量。

inf（infinite）表示无穷大的一个数，用十六进制0x3f3f3f3f表示，具体见https://blog.csdn.net/jiange_zh/article/details/50198097

这段代码在实现Dijkstra时，并没有像通常的那样把dis初始化成起点到相邻点的距离，而是只把dis[s]=0，其他全部是无穷大。这个初始化是因为每次都要记录很多东西，如果直接把dis初始化成起点到相邻点的距离，还需要把相邻点的path，path_num，sum再写一遍。但是如果只把dis[s]=0，其他为无穷大，其实就是现在的最小生成树是一个空树，第一步当然是把起点s加入到最小生成树，而这里的代码已经在更新时写过了。以后写也可以把dis这样初始化。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>
#include <vector>
#include <cmath>
#include <cstring>
#include <map>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
 
int n,m,s,d;
int a[510][510],vis[510],dis[510];
int path[510],path_num[510],sum[510],w[510];
//path记录上一个点，path_num最短路径条数，sum救援队总数，w每个点的救援队数量
 
void way(int x)
{
    if(path[x]==-1){
        cout<<x;
        return;
    }
    else{
        way(path[x]);
        cout<<" "<<x;
    }
}
 
void dijkstra()
{
    for(int i=0;i<n;i++) dis[i] = inf;
    dis[s] = 0;
    path[s] = -1;
    path_num[s] = 1;
    sum[s] = w[s];
    while(1){
        int u,min=inf;
        for(int i=0;i<n;i++){
            if(!vis[i]&&min>dis[i]){
                min = dis[i];//记录距离最小值
                u = i;//记录最小值的下标
            }
        }
        if(min==inf) return;//如果没有可以到达的点，结束
        vis[u] = 1;
 
        for(int i=0;i<n;i++){
            if(dis[i]>dis[u]+a[u][i]){
                dis[i] = dis[u] + a[u][i];
                path[i] = u;
                path_num[i] = path_num[u];
                sum[i] = sum[u] + w[i];
            }
            else if(dis[i]==dis[u]+a[u][i]){//如果距离相等
                path_num[i] += path_num[u];//最短路径数量应是两者之和
                if(sum[i]<sum[u]+w[i]){    //如果新的路径救援队数量更多，更改最优路径
                    sum[i] = sum[u] + w[i];
                    path[i] = u;
                }
            }
        }
 
    }
}
 
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&d);
    for(int i=0;i<n;i++)
        scanf("%d",&w[i]);
    int x,y,t;
 
    memset(a,inf,sizeof(a));
 
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&t);
        a[x][y]=a[y][x]=t;
    }
    dijkstra();
    printf("%d %d\n",path_num[d],sum[d]);
    way(d);
    return 0;
 
}