PAT 1003 Emergency（单源最短路径+Dijkstra）

原题地址

https://www.patest.cn/contests/pat-a-practise/1003

题意：给定N个城市以及M条城市之间的道路，每座城市有自己的权重city[i]，每条道路也有自己的权重cost[i][j]，求源顶点v0到目标顶点vt的最短路径的数量，以及沿着最短路径的累加顶点权重的最大值。

解题思路

本题是单源最短路径的变形题，寻找单源最短路径一般用Dijkstra算法就可以直接。

关于两种求最短路径算法的总结详见最短路径—Dijkstra算法和Floyd算法

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

该算法把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

对于这一题来说，由于结果不关心最短路径的长度，但是关心最短路径的条数，以及这些最短路径上最大的顶点权重之和，所以一共需要维护一下变量、数组：

visit[i]标记顶点i是否已经求得最短路径city数组记录每个顶点的权重，cost数组记录每条边的权重dist[i]记录源点 v0 到顶点 i 的最短距离.若i已经在S中，则该距离即v0到i的最短路径长度；若i不在S中，则该距离即v0只通过S中的顶点到达i的最短路径长度 和Prim算法的最大区别就是Prim-dist对子集S维护，而Dijkstra算法对源点v0维护。pathCount[j]维护源点v0到顶点j的最短路径的条数，amount[i]维护源点v0到顶点j的最短路径上的最大顶点权重之和

因此本题的关键就是在算法核心部分—松弛（Relax）时维护dist，pathCount，amount这三个数组。

假设 j 满足从源点v0通过S中的顶点到 j 的距离dist[j]最小，那么看能否经由 j 到S外的顶点的距离更小。若通过 j 到 k的距离 小于 v0通过之前S中的顶点到 k 的距离，则更新dist[k]的同时，更新pathCount[k]为pathCount[j]，更新amount[k]为amount[j]+city[k]。上面的松弛情况还是比较好理解的，但是不能遗漏另一种情况，如果这两个距离相等怎么办？那就要为pathCount[k]加上pathCount[j]这些路，同时看看amount[k]能否取得更大。

注意v0到自己时的情况，下面的代码已经对此优化。

AC代码

#include "iostream" #include "cstring" using namespace std; const int maxn = 505, INF = 0x3f3f3f3f; int city[maxn]; //每个顶点的值 int cost[maxn][maxn]; //每条边的权重 int dist[maxn]; //从v0到j的边权重最小值 int pathCount[maxn], amount[maxn]; //v0到j的最短路径数和累计顶点值 bool visit[maxn]; //标记已经求出最短路径的顶点 int n, m; void init() { memset(visit, false, sizeof(visit)); for (int i = 0; i<n; ++i) { pathCount[i] = amount[i] = 0; for (int j = 0; j<n; ++j) cost[i][j] = (i == j)? 0: INF; } } void Dijkstra(int v0) //求v0到各个顶点的最短路径 { //v0直接到自己最短 pathCount[v0] = 1; amount[v0] = city[v0]; visit[v0] = true; //生成最初的dist数组 for (int i = 0; i<n; ++i) { dist[i] = cost[v0][i]; if (dist[i] != INF && i != v0) { amount[i] = amount[v0] + city[i]; pathCount[i] = 1; } } for (int i = 0; i < n-1; ++i) //处理剩余n-1个顶点 { //找当前v0到j的最短路径 int min_dist = INF, pos = -1; for (int j = 0; j<n; ++j) { if (!visit[j] && dist[j] < min_dist) //别选已经visit了的顶点！ { min_dist = dist[j]; pos = j; } } visit[pos] = true; //标记访问 //更新v0到各点的路径长度 for(int j = 0; j<n; ++j) { //松弛，通过pos到j更近 if (!visit[j] && dist[pos]+cost[pos][j] < dist[j]) { dist[j] = dist[pos] + cost[pos][j]; //通过pos到j amount[j] = amount[pos] + city[j]; //累加顶点的值 pathCount[j] = pathCount[pos]; //到j的最短路径数即到pos的最短路径数 } //直接到j和通过pos到j的距离相等 else if (!visit[j] && dist[pos]+cost[pos][j] == dist[j]) { pathCount[j] += pathCount[pos]; //增加从pos到j的路径数量 if (amount[j] < amount[pos]+city[j]) //更新较大的amount amount[j] = amount[pos]+city[j]; } } } return; } int main(int argc, char const *argv[]) { ios::sync_with_stdio(false); int v0, vt; cin >> n >> m >> v0 >> vt; init(); for (int i = 0; i < n; ++i) cin >> city[i]; int t1,t2,t; for (int i = 0; i < m; ++i) { cin >> t1 >> t2 >> t; cost[t1][t2] = cost[t2][t1] = t; } Dijkstra(v0); cout << pathCount[vt] << ' ' << amount[vt] << endl; return 0; }

算法复杂度：O(n^2) 耗时：10 ms

附一个知乎讨论：迪杰斯特拉算法(Dijkstra)的本质是贪心还是动态规划?