PAT 1003 Emergency (25分)

题目链接：点击这里

题意：作为一个城市的紧急救援队队长，你会得到一张你国家的特殊地图。这张地图显示了由几条道路连接起来的几个分散的城市。地图上标出每个城市的救援队伍数量和每对城市之间的道路长度。当你接到来自其他城市的紧急电话时，你的任务是带领你的人尽快到达目的地，同时在路上尽可能多地召集人手。数据保证至少存在一条路径。

思路：题目给出了一个第二标尺（第一标尺是距离），要求在所有最短路径中选择第二标尺最优的一条路径。

新增点权。用 $weight[u]$ 表示城市 $u$ 中的救援队伍数量，并增加一个数组 $w[]$，令从起点 $s$ 到达顶点 $u$ 可以召集到的最多人手为 $w[u]$，初始化时只有 $w[s]$ 为 $weight[s]$、其余 $w[u]$ 均为 $0$。

当 $d[u]+g[u][v]<d[v]$（即可以使 $s$ 到 $v$ 的最短距离 $d[v]$ 更优）时更新 $d[v]$ 和 $w[v]$

当 $d[u]+g[u][v]==d[v]$（即最短距离相同）且 $w[u]+weight[v]>w[v]$（即可以使 $s$ 到 $v$ 的最多人手数更优）时更新 $w[v]$。

求最短路径条数。只需要增加一个数组 $cnt[]$，令从起点 $s$ 到达顶点 $u$ 的最短路径条数为 $cnt[u]$，初始化时只有 $cnt[s]$ 为 $1$、其余 $cnt[u]$ 均为 $0$。

当 $d[u]+g[u][v]<d[v]$（即可以使 $s$ 到 $v$ 的最短距离 $d[v]$ 更优）时更新 $d[v]$，并让 $cnt[v]$ 继承 $cnt[u]$

当 $d[u]+g[u][v]==d[v]$（即最短距离相同）时将 $cnt[u]$ 加到 $cnt[v]$ 上。

AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 510; int g[N][N], d[N]; bool st[N]; int weight[N], w[N]; int cnt[N]; int n, m, src, dst; void dijkstra() { memset(d, 0x3f, sizeof d); d[src] = 0, cnt[src] = 1, w[src] = weight[src]; for(int i = 0; i < n; i++) { int t = -1; for(int j = 0; j < n; j++) if(!st[j] && (t == -1 || d[t] > d[j])) t = j; st[t] = true; for(int j = 0; j < n; j++) { if(d[j] > d[t] + g[t][j]) { d[j] = d[t] + g[t][j]; cnt[j] = cnt[t]; w[j] = w[t] + weight[j]; } else if(d[j] == d[t] + g[t][j]) { cnt[j] += cnt[t]; w[j] = max(w[j], w[t] + weight[j]); } } } } int main() { scanf("%d%d%d%d", &n, &m, &src, &dst); for(int i = 0; i < n; i++) scanf("%d", &weight[i]); memset(g, 0x3f, sizeof g); for(int i = 0; i < m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a][b] = g[b][a] = min(g[a][b], c); } dijkstra(); printf("%d %d\n", cnt[dst], w[dst]); return 0; }

微信公众号《算法竞赛求职》，致力于详细讲解竞赛和求职所涉及到的算法原理和模板。欢迎关注，一起交流进步！