学习目标
前置知识
完成 Lab 07-E-16：Dijkstra 逐轮推演与 Lab 07-E-18：网络延迟时间。本题需要在求最短距离的同时维护路径条数与最大救援队数，改编自浙大 PAT 1003（Emergency）。
题目背景
一张无向地图上有 n 个城市，编号 0..n-1。每个城市有若干支救援队。你从出发城市 s 出发，要去目标城市 t。
- 求：从
s到t的最短路径条数； - 在这些最短路径中，能召集到最多救援队的数量（路径上所有城市救援队之和）。
两个输出依次打印。
关键思想：一份松弛，三份账本
Dijkstra 原来的 prev 只记录一条前驱；本题需要记录的是"有多少种方式到达"与"每种方式最多能带多少救援队"。于是除了 dist，再维护两个数组：
| 数组 | 含义 | 初始化 |
|---|---|---|
cnt[v] | 从 s 到 v 的最短路径条数 | cnt[s] = 1，其余 0 |
sum[v] | 所有最短路径中能召集的最大救援队数 | sum[s] = c[s]，其余 0 |
松弛一条边 (u, v, w) 时，分两种情况：
- 更短（
dist[u] + w < dist[v]）：旧的最短路全部作废。dist[v]更新；cnt[v] = cnt[u]；sum[v] = sum[u] + c[v]； - 等长（
dist[u] + w == dist[v]）：新发现同长度路径。cnt[v] += cnt[u]；sum[v] = max(sum[v], sum[u] + c[v])。
实现时先计算候选距离 candidate = dist[u] + w，再与当前 dist[v] 比较。候选距离严格更小时，覆盖 dist[v]、cnt[v] 和 sum[v]；候选距离相等时，保持 dist[v] 不变，只累加路径条数并更新最大救援队数。不要只比较单条边权 w。
输入格式
第一行四个整数 n m s t：城市数、道路数、出发城市、目标城市。
第二行 n 个整数 c[0..n-1]：每个城市的救援队数量。
接下来 m 行，每行三个整数 u v w，表示城市 u 与 v 之间有一条无向路，路长 w。
输入保证：
2 <= n <= 500；0 <= m <= 2*10^5；0 <= u, v < n（允许自环与多重边）；0 <= c[i] <= 200；1 <= w <= 10^4；0 <= s, t < n且s != t，从s到t至少存在一条路径；- 最短路径条数保证不超过
long long可表示范围。
输出格式
一行两个整数：最短路径条数 与 最多救援队数量，用空格分隔。
样例输入
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1样例输出
2 4样例解释
从城市 0 到 2 的最短路长 2，有两条：0→1→2 与 0→2。
0→1→2召集1+2+1 = 4支救援队；0→2召集1+1 = 2支。
输出条数 2、最多救援队 4。
任务
- 读入点权数组与无向边表，把每条无向边拆成两条有向边存入邻接表；
- 朴素或堆优化 Dijkstra，松弛时按"更短 / 等长"两个分支维护
cnt与sum； - 输出
cnt[t]与sum[t]。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 两条等长路径汇入同一点 | cnt 相加，sum 取更大者 |
| 一条路径中间被更短路径覆盖 | 旧 cnt/sum 整体作废重算 |
| 点权越大路径越长 | 按距离优先，sum 只在同距离内比较 |
| 多重无向边 | 每条道路视为独立道路；等权平行边分别计入路径条数，较重边只有在不影响最短路时才不会计入 |
| 最短路径条数超过 32 位 | 010-long-long-path-count 构造 cnt 必须使用 long long |
n=500 稠密图 | 朴素 cnt 用 long long |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-21-emergency-rescue
pnpm lab:run -- labs/chapter-07/exercise/E-07-21-emergency-rescue
pnpm lab:score -- labs/chapter-07/exercise/E-07-21-emergency-rescue完成清单
解题思路
Dijkstra 松弛时同时维护最短距离、达到该距离的路径条数和路径上救援队总数。距离更短时三项全部替换，距离相等时累加路径数并保留更大的救援队数。
复杂度分析
朴素版 cnt 与 sum 都必须已经收敛。请思考：为什么"确定顶点时 cnt 已收敛"成立？这和 Dijkstra 的确定性不变量是同一回事。
思考与复盘
- 为什么等长分支要
cnt[v] += cnt[u]而不是cnt[v] = max(...)？
查看参考答案
cnt 表示路径数量，不是路径上的某个可比较分值。若 (u,v,w) 产生与 dist[v] 相等的距离，那么每一条到 u 的最短路拼接这条边，都会形成一条到 v 的新最短路，因此应全部累加；取最大值会丢失其他合法路径。
- 若图中有零权边，朴素版选点后还能保证
cnt立即收敛吗？会出什么问题？如何修正？
查看参考答案
不能保证。零权边可连接同一距离层的两个顶点：v 已确定后，另一个同距离顶点才把新的等长路径计入 cnt[v]，这份新增计数却不会再向 v 的后继传播。若存在可达零权环，最短“走法”甚至可以无限多。当前题面以 w >= 1 排除该问题；若要支持零权边，应先明确只计简单路径，并按距离分层处理、压缩零权强连通分量或建立无环的层内依赖关系。
- 若题目改为"在所有最短路中救援队最少的一条"，
sum的初始化与更新要改哪里？
查看参考答案
把非源点的 sum 初始化为足够大的 INF，仍令 sum[s]=c[s]。发现更短路时直接赋 sum[u]+c[v]；发现等长路时把 max 改为 min。cnt 和 dist 的更新规则不变。
- 如果想把这条路径也输出（多条时输出字典序最小的），
prev应该存成什么？
查看参考答案
只输出一条时 prev[v] 仍可存被选中路径的单个前驱。严格变短时直接改写；等长且救援队数相同或满足题设优先级时，必须比较“源点到前驱”的完整顶点序列，再决定是否替换，不能只比较前驱编号。也可以临时保存完整路径或提供前驱链比较函数。