[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
百威成长空间 50人发布
