[PAT解题报告] Emergency
题目给了一个图,代表若干个城市,每个城市里有若干人,城市靠道路相连——总体来说是一个无向图,每个节点有一个权值,边也有权值,代表路径长度。然后给定一个起点,是你所在的城市,再给定一个终点——表示目的城市,一旦遇到紧急情况,你需要以最快的速度把尽可能多的人放到目的城市。求两个值
(1) 从起点到终点有多少条最短路径 (2) 走最短路的前提下,你最多能运送多少人到终点?
分析:
这是一个典型的最短路问题。后面还会看到其实PAT最短路的问题还挺多的,但都不是直接求最短路那么简单。比如本题,还要求最短路的长度。我们考虑一下Dijkstra算法的核心步骤:
if (d[i] > d[j] + w(j, i)) then d[i] = d[j] + w(j, i)
其中j是我们目前还没有用过的距离最小的点, w(j, i)表示j到i的距离,我们会用d[j] + w(j,
i)更新d[i]的最小距离。
如何计算最短路的条数呢? 玄机也在这里!我们用数组way[x]表示从起点到x的最短路条数。
如果d[i] == d[j] + w(j, i) 原来达到j的最短路加上边(j,i)也是达到j的最短路,于是累加way[i] +=
way[j]。
如果d[i] > d[j] + w(j, i) 我们更新d[i] = d[j] + w(j,
i)的同时,得到了更从起点到j更短的路,所以之前的计算的条数没有意义了,直接有way[i] = way[j]
那么怎样计算最多运送的人数呢?
也是类似的。我们用num[x]表示从起点到达x走最短路能运送的最多的人数。并且b[x]表示在x处有多少人。
如果d[i] == d[j] + w(j, i), num[i] = max(num[i], num[j] + b[i])
这是因为我们选择是否从j走到i要看经过j是不是比我们现在带的人多。
如果d[i] > d[j] + w(j, i), 更新d[i] = d[j] + w(j,
i)的同时,我们只能用num[i] = num[j] +
b[i],因为我们一定要优先走最短路——带的人数是第二关键字,所以我们别无选择,只能选择经过j。
因此,本题关键在于理解dijkstra算法更新的过程,以及最短路的形成——其实本质就是s到i的最短路,包含了s到j的最短路,加上j到i的那条边的长度——一切更新都源于此。
注意: 我假设了两个点间的最短边只有一条,如果有平行边(两点间最短的边有多个),要记录一下最短边的条数,更新的时候
way[i] = way[k] * edge_count[i, k] 或者way[i] += way[k] * edge_count[i, k]edge_couint [i, k] 表示i,k之间有多少条边都是最短长度的…… 邻接矩阵要多存一个值。
代码:
#include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int inf = 1000000000; const int N = 502; int n; bool mark[N]; int a[N][N]; int num[N]; int b[N]; int cost[N]; int way[N]; void dijkstra(int s) { for (int i = 0; i < n; ++i) { cost[i] = inf; mark[i] = false; num[i] = way[i] = 0; } num[s] = b[s]; way[s] = 1; cost[s] = 0; for (int j = 0; j < n; ++j) { int k = -1; for (int i = 0; i < n; ++i) { if ((!mark[i]) && ((k < 0) || (cost[i] < cost[k]))) { k = i; } } mark[k] = true; for (int i = 0; i < n; ++i) { if ((!mark[i]) && (a[k][i] < inf)) { int temp = cost[k] + a[k][i]; if (temp < cost[i]) { cost[i] = temp; num[i] = num[k] + b[i]; way[i] = way[k]; } else if (temp == cost[i]) { num[i] = max(num[k] + b[i], num[i]); way[i] += way[k]; } } } } } int main() { int m,from,to; scanf("%d%d%d%d",&n,&m,&from,&to); for (int i = 0; i < n; ++i) { scanf("%d",b + i); for (int j = 0; j < n; ++j) { a[i][j] = inf; } } for (;m;--m) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x][y] = a[y][x] = min(a[x][y],z); } dijkstra(from); printf("%d %d\n",way[to], num[to]); return 0; }
原题链接: http://www.patest.cn/contests/pat-a-practise/1003