【天梯赛】L2-001紧急救援（用迪杰斯特拉找出权重和最小的最短路径）

 解题反思

尝试DFS：开始使用DFS来遍历求解，但 DFS 存在大量重复计算，像同一节点会被多次访问并重复计算路径信息，导致时间复杂度高，部分测试点未通过

改用迪杰斯特拉：为了求解，设置了很多的辅助数组，对于他们本身的初始化、以及对于起始点S的初始化赋值容易出错，需要小心

迪杰斯特拉相当于是用一次过程找出了所有点的信息，最后只需要按要求输出D对应的信息即可

迪杰斯特拉算法，通过储存每个点的信息，为后续的其他点的信息求取打下了坚实基础，用空间换取了大量时间

题面

L2-001 紧急救援 - 团体程序设计天梯赛-练习集

代码实现 

// 定义常量 mx 为整型的最大值，用于表示无穷大
#define mx INT_MAX
#include<bits/stdc++.h>
using namespace std;int main()
{// N 表示城市数量，M 表示道路数量，S 表示起点城市，D 表示终点城市int N,M,S,D;// 从标准输入读取 N、M、S、D 的值cin>>N>>M>>S>>D;// 创建一个大小为 N 的向量 rescue，用于存储每个城市的救援人员数量vector<int>rescue(N);// 循环 N 次，依次读取每个城市的救援人员数量并存入 rescue 向量for(int i=0; i<N; i++) cin>>rescue[i];// 创建一个 N * N 的二维向量 graph，初始值都为 mx（无穷大），用于表示城市间的距离vector<vector<int>>graph(N, vector<int>(N, mx));// 循环 M 次，读取每条道路的信息for(int i=0; i<M; i++){// a 和 b 表示道路连接的两个城市，len 表示道路的长度int a, b, len;// 从标准输入读取 a、b、len 的值cin>>a>>b>>len;// 无向图，两个城市间的距离是对称的，更新 graph 矩阵graph[a][b] = len;graph[b][a] = len;}//// 存储从起点到每个城市的最短距离，初始值为 mx（无穷大）vector<int>dist_(N, mx);// 存储从起点到每个城市能召集到的最大救援人员数量，初始值为 0vector<int>re_rescue(N, 0);// 存储从起点到每个城市的最短路径数量，初始值为 0vector<int>path_cnt(N, 0);// 标记每个城市是否已经确定最短路径，初始值为 falsevector<bool>visited(N, false);// 存储每个城市在最短路径中的前驱城市，初始值为 -1vector<int>pre(N, -1);//// 起点到自身的距离为 0dist_[S] = 0;// 起点的前驱城市是自身pre[S] = S;// 起点到自身的最短路径数量为 1path_cnt[S] = 1;// 起点能召集到的救援人员数量就是起点城市本身的救援人员数量re_rescue[S] = rescue[S];// 迪杰斯特拉算法核心循环，循环 N 次for(int i=0; i<N; i++){// 用于记录当前未确定最短路径的城市中距离起点最近的城市编号，初始值为 -1int u = -1;// 记录当前找到的最小距离，初始值为 mx（无穷大）int min_len = mx;// 遍历所有城市for(int j=0; j<N; j++){// 如果该城市未确定最短路径且距离起点的距离小于当前最小距离if(!visited[j] && dist_[j] < min_len){// 更新最小距离min_len = dist_[j];// 更新最近城市编号u = j;}}// 如果没有找到符合条件的城市，说明所有可达城市都已确定最短路径，退出循环if(u == -1) break;// 标记该城市已确定最短路径visited[u] = true;// 遍历所有城市，更新与 u 相邻城市的信息for(int j=0; j<N; j++){// 如果 u 到 j 有道路且通过 u 到 j 的距离比当前记录的距离更短if(graph[u][j] != mx && dist_[j] > dist_[u] + graph[u][j]){// 更新 j 到起点的最短距离dist_[j] = dist_[u] + graph[u][j];// 更新 j 的前驱城市为 upre[j] = u;// 更新 j 的最短路径数量为 u 的最短路径数量path_cnt[j] = path_cnt[u];// 更新 j 能召集到的最大救援人员数量re_rescue[j] = re_rescue[u] + rescue[j];}// 如果 u 到 j 有道路且通过 u 到 j 的距离与当前记录的距离相等else if(graph[u][j] != mx && dist_[j] == dist_[u] + graph[u][j]){// 累加 j 的最短路径数量path_cnt[j] += path_cnt[u];// 如果通过 u 到 j 能召集到更多的救援人员if(re_rescue[j] < re_rescue[u] + rescue[j])//比较救援人数大小{// 更新 j 的前驱城市为 upre[j] = u;// 更新 j 能召集到的最大救援人员数量re_rescue[j] = re_rescue[u] + rescue[j];}}}}// 输出从起点到终点的最短路径数量和能召集到的最大救援人员数量cout<<path_cnt[D]<<" "<<re_rescue[D]<<endl;// 回溯找路径// 创建一个栈 help 用于存储路径stack<int>help;// 从终点开始回溯int cur = D;// 将终点压入栈中help.push(cur);// 当当前城市的前驱城市不是自身时，继续回溯while(pre[cur] != cur){// 更新当前城市为其前驱城市cur = pre[cur];// 将当前城市压入栈中help.push(cur);        }// 依次弹出栈中的元素并输出路径while(!help.empty()){// 获取栈顶元素cur = help.top();// 弹出栈顶元素help.pop();// 输出当前城市编号cout<<cur;// 如果栈不为空，输出空格分隔if(help.empty()) break;cout<<" ";}// 换行cout<<endl;return 0;     
}

~希望对你有启发！~