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

 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 }