L2-001-紧急救援*C++(使用Dijkstra算法附带全详细注释）

2023-03-28 22:24 由神雨临发表于 #后端开发

L2-001 紧急救援

分数 25

作者陈越

单位浙江大学

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

输入格式:

输入第一行给出4个正整数

第二行给出

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从

输入样例:

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

代码长度限制

16 KB

时间限制

200 ms

内存限制

64 MB

解题思路：

从题目信息中可得到"道路长度"和"城市救援队"这俩个玩意，于是可以联想到带权图与最短路径问题，我们可以将城市看作节点，道路看作连接节点之间的路径，而每个城市都有一定数量的救援队(城市的权值）同时每条道路都有距离，与此同时根据该图不可能存在负权值的边，而且起点与终点是固定的，那么根据这些信息我们可以确定本题需要用到Dijkstra算法。

与此同时在Dijkstra算法基础上需要考虑三个变量，一个是最短路径的数量road[]，另一个是在最短路径的中救援队最多的数量total[]，最后一个是前面俩个前提下的路径path[]

于是我在这道题中还用使用到了优先队列priority_queue函数，后来总结发现其实这道题还有动态规划的思想在里面，如果还打算优化的话还能使用弗洛伊德+迪杰斯特拉组合或最小索引堆来进行算法效率的提升（但由于本人技术实在有限就没考虑那么多了T.T）

代码部分：

 1 //#include<bits/stdc++.h> 不建议使用万能头文件
 2 #include<iostream>
 3 #include<set>
 4 #include<cstring>
 5 #include<queue>
 6 #define ll long long; // 定义long long类型 
 7 using namespace std;
 8 
 9 const int inf = 0x3f3f3f3f;//无穷大 
10 typedef pair<int, int>PII;
11 int n, m, s, d;                        //dis[i]表示当前起点到i点的最短距离 
12 int mp[510][510], vis[510], dis[510];//vis数组的作用是记录每个节点是否已被访问过。在Dijkstra算法中，每次从队列中取出距离起点最短的节点时，需要判断该节点是否已经被访问过。若该节点已被访问过，则可以直接跳过，因为它的最短路径已经求得，不需要再次计算。因此，vis数组可以避免重复计算，提高程序的效率。
13 int total[510], city[510], path[510], road[510];//road记录从起点到每个节点的最短路径数量,path[i]表示i节点的最短前驱节点,total[i] 表示从起点到i节点的最短路径的救援人员数总和 
14 
15 void dijkstra()
16 {
17     memset(dis, 0x3f, sizeof(dis)); // 初始化距离为无穷大 
18     total[s] = city[s]; // 初始点的总点权值为其本身的点权值 
19     path[s] = -1; // 初始点没有前驱节点 
20     road[s] = 1; // 初始点到达方式为一种 
21     dis[s] = 0; // 起点到起点的距离为0 
22     //采用优先队列的路线是：先摸出第一条最短路径，(因为这道题还需要找相同距离的可能以及相同距离中救援队最多的情况)所以还需要依次再摸出第二条第三条...的最短路径 
23     //也就是说最短路径的下一个最短 节点会被优先访问 
24     priority_queue<PII>q;//优先队列当存储的是一组数据时默认第一个数据是权值，存储的是pair类型（距离，节点） 用堆q存储最短距离节点(当节点数量多时用最短距离优先队列可以提高效率) 
25     q.push({ 0,s });// 将起点加入队列 
26     while (q.size())
27     {
28         int now = q.top().second; // 取出队首元素的节点 
29         q.pop(); // 删除队首元素 
30         if (vis[now]) // 若当前节点已被访问过，则跳过 
31             continue; 
32         vis[now] = 1; // 标记当前节点已被访问 
33         for (int i = 0; i < n; i++)
34         {
35             if (mp[now][i])//(判断now到i是否存在路径)用now节点去访问所有的节点来找到最短路径 
36             {
37                 if (dis[i] > dis[now] + mp[now][i]) // (dis[i]在i被访问前都是无穷大)若通过当前节点到达其它节点更近，则更新信息 
38                 { 
39                     path[i] = now; // 更新前驱节点(i的前驱节点为now) 
40                     total[i] = total[now] + city[i]; // 更新总点权值(到i的救援队总数为now的总和+城市i的数量) 
41                     dis[i] = dis[now] + mp[now][i]; // 更新距离 
42                     road[i] = road[now]; // *更新到达方式 
43                     if(i!=d)
44                         q.push({ -dis[i],i }); // 将更新后的节点加入队列中 (采用负数是因为希望最近的被优先处理,使得更小的距离对应更高的优先级。) 
45                 }
46                 else
47                 {
48                     if (dis[i] == dis[now] + mp[now][i]) // 若路径相同，则更新路径数量和总点权值 
49                     {
50                         //也就是说在 "now到i的距离mp[now][i]+now的最短距离dis[now]等于i的最短距离dis[i]" 的前提下从起点到i的新的最短路径数量等于 起点到i的最短路径数road[i]加上起点到now的最短路径数road[now]
51                         //最短路径树的延长(可以画张图理解) 
52                         road[i] += road[now]; // ***更新路径数量 
53                         if (total[i] < total[now] + city[i]) // 若当前节点的总点权值更大，则更新 
54                         {
55                             total[i] = total[now] + city[i];
56                             path[i] = now;
57                         }
58                     }
59                 }
60             }
61         }
62     }
63 }
64 
65 int main()
66 {
67     cin >> n >> m >> s >> d;
68     for (int i = 0; i < n; i++)
69         cin >> city[i]; // 输入每个城市的点权值 
70     for (int i = 0; i < m; i++)
71     {
72         int x, y;
73         cin >> x >> y;
74         cin >> mp[x][y];
75         mp[y][x] = mp[x][y]; // 无向图，因此需要将两个方向的边权值都赋值 
76     }
77 
78     dijkstra(); // 调用Dijkstra算法求解最短路径 
79     int now = d;
80     vector<int>answer; // 存储最短路径 
81     while (now != -1)
82     {
83         answer.push_back(now);
84         now = path[now]; // 逆序遍历路径，找到所有经过的节点 
85     }
86     cout << road[d] << " " << total[d] << endl; // 输出到达终点的路径数量和总点权值 
87 
88     for (int i = (int)answer.size() - 1; i > 0; i--)
89         cout << answer[i] << " ";
90     cout << answer[0]; // 输出从起点到终点的最短路径 
91 
92     return 0;
93 }