学习目标

• 能用邻接矩阵存稠密带权图（多重边取最小、自环忽略）；
• 能实现严蔚敏教材风格的朴素 $O(n^2)$ Dijkstra；
• 能用 prev 前驱数组把任意目标的最短路径完整还原成顶点序列；
• 能区分"距离"与"路径"两个输出层次，并正确处理不可达目标。

前置知识

完成 Lab 07-E-16：Dijkstra 逐轮推演后再来。你需要理解：在稠密图（$m\approx n^2$）上，朴素版的 $O(n^2)$ 为什么可能优于堆版的 $O((n+m)\log n)$。原因是堆版可能产生 $O(n^2)$ 条堆记录，并且每次入堆、出堆还要付出对数时间。

输入格式

第一行包含四个整数 n m q s，分别表示顶点数、有向边数、查询数与源点编号。顶点编号为 0 到 n-1。

接下来 m 行，每行三个整数 u v w，表示一条从 u 指向 v 的有向边，边权为 w。

最后一行 q 个整数 t1 t2 ... tq，表示依次查询从源点 s 到各目标的最短路径。

输入保证：

• 1 <= n <= 1000；
• 0 <= m <= 10^5；（本题按较稠密图设计，但不要求达到 n=1000 的完全图规模。）
• 0 <= u, v < n（允许自环与多重边，邻接矩阵存图时自环忽略、多重边取最小权）；
• 0 <= w <= 10^4；
• 0 <= s < n；
• 1 <= q <= 1000，0 <= ti < n。

输出格式

输出 q 行。第 i 行回答查询 ti：

• 可达时输出 dist 与完整路径顶点序列，格式为 dist: v0 v1 ... vk（v0 = s，vk = ti）；
• 不可达时输出 -1；
• ti == s 时输出 0: s。

样例输入

6 10 5 0
0 1 1
0 2 4
0 5 10
1 2 8
1 3 3
2 3 1
2 4 5
3 4 2
3 5 6
4 5 1
5 0 3 2 1

样例输出

7: 0 1 3 4 5
4: 0 1 3
6: 0 1 3 4
4: 0 2
1: 0 1

样例解释

沿用教材 7.3 节配送图。查询 0→5 的最短路是 $A\to B\to D\to E\to F$（权 $7$）；查询 0→2 有直达边（权 $4$），它比 $A\to B\to C$（$1+8=9$）更短。prev 链为 5←4←3←1←0，回溯后反转即得正序路径。

任务

1. 读入边表，构造邻接矩阵：adj[u][v] = min(adj[u][v], w)，自环（u == v）直接忽略；无边用无穷大标记；
2. 跑一遍朴素 Dijkstra（与 Lab 07-E-16 相同：每轮选择未确定且 dist 最小的顶点，并列时选编号最小者），维护 dist 与 prev；
3. 对每个查询目标：沿 prev 从目标回溯到源点，收集顶点后反转输出；
4. 回溯前必须先判不可达（dist[t] 为无穷），避免无效回溯甚至死循环。

正常、边界与错误情况

情况	预期行为
目标不可达	输出 -1，不进入回溯
目标即源点	输出 0: s
多重边	邻接矩阵取最小权后再跑算法
自环	建图时忽略
直达边不是最优	正确输出绕行路径（如样例中的 0→5）
平手距离	prev 由严格小于的松弛规则唯一确定
较稠密大图	n=1000、m<=10^5 时仍按矩阵的 $O(n^2)$ 复杂度完成；完全图规模不属于本题输入范围

运行与评分

在本 Lab 目录执行：

make doctor
make run
make run CASE=001-sample
make score

未安装 Make 时，在仓库根目录执行：

pnpm lab:doctor -- labs/chapter-07/exercise/E-07-17-dijkstra-matrix-path
pnpm lab:run -- labs/chapter-07/exercise/E-07-17-dijkstra-matrix-path
pnpm lab:score -- labs/chapter-07/exercise/E-07-17-dijkstra-matrix-path

完成清单

• 全部测试用例通过；
• 邻接矩阵建图时处理好多重边（取最小）与自环（忽略）；
• prev 回溯对"目标即源点"正确输出单点路径；
• 不可达目标不会触发回溯；
• 稠密图用例在时限内通过。

解题思路

使用邻接矩阵实现朴素 Dijkstra，dist 保存当前最短距离，prev 保存产生改进的前驱。查询目标时沿前驱反向回溯，再反转得到从源点出发的路径。

复杂度分析

建图 $O(n^2)$（矩阵初始化），Dijkstra 朴素 $O(n^2)$，q 次回溯每次 $O(n)$。总计 $O(n^2+qn)$。对 n=1000、q=1000 约 $3\times {10}^6$ 量级；即使 m 达到本题上限 10^5，主要成本仍由矩阵扫描决定。若把同一规模扩展到完全图，输入规模和资源需求会另行增加，不属于本题约束。

思考与复盘

1. 回溯 prev 时如果路径中有环（例如 prev 被错误更新成指向后代），会发生什么？如何用"路径长度上界"防御？

查看参考答案

回溯不会到达 -1 或源点，会陷入无限循环。无环最短路径至多包含 n 个顶点，因此可额外维护步数；若回溯超过 n 步仍未到源点，就把它视为前驱链损坏并停止报告错误。

2. 本题输出路径只需回溯 prev；若要求输出所有等长最短路径，需要把 prev 改成什么结构？

查看参考答案

应改为“前驱集合”，例如 vector<vector<int>> predecessors：严格变短时清空并加入当前前驱，等长时追加当前前驱。之后从目标沿此前驱 DAG 做 DFS/回溯枚举；路径数量可能指数级，接口还应考虑数量上限或只计数。

3. 邻接矩阵版本对 n=1000 的稀疏图（m=1000）是否浪费？浪费体现在哪两个维度？

查看参考答案

是。空间上矩阵固定占 $O(n^2)$，而邻接表只需 $O(n+m)$；时间上每个已确定顶点仍要扫描整行 n 个位置，Dijkstra 是 $O(n^2)$，无法利用只有约 m 条边的稀疏性。

4. 无向图如何用本框架表达？路径输出会有什么不同？

查看参考答案

每条输入边 (u,v,w) 同时写入 adj[u][v] 与 adj[v][u]，其余 Dijkstra 和 prev 回溯逻辑不变。输出仍是从源点到目标点的顶点序列；只是任一路径反向走也合法。