学习目标
前置知识
完成前建议先阅读第 7.3 节 最短路径（重点看"第二幕 · Dijkstra 的贪心"与手算表）。你需要准备支持 C++17 的编译器；可先运行 make doctor 检查环境。
输入格式
第一行包含三个整数 n m s，分别表示顶点数、有向边数与源点编号。顶点编号为 0 到 n-1。
接下来 m 行，每行包含三个整数 u v w，表示一条从 u 指向 v 的有向边，边权为 w。输入保证：
1 <= n <= 1000；0 <= m <= 5000；0 <= u, v < n（允许u == v的自环；允许多重边）；0 <= s < n；0 <= w <= 10^4（边权非负，这是 Dijkstra 的前提）。
输出格式
输出三行：
第一行 n 个整数，dist[i] 为源点到顶点 i 的最短距离，不可达输出 -1；
第二行 n 个整数，prev[i] 为最短路径上 i 的前驱顶点，源点与不可达顶点输出 -1；
第三行按"被确定"的先后顺序输出所有可达顶点的编号（朴素版每轮恰好确定一个顶点，源点第一个确定）。
平手规则
每轮在未确定且 dist 有限的顶点中，选 dist 最小者；若有并列，选编号最小者。这条规则让输出唯一可判，也正是考研手推题的阅卷约定。
样例输入
6 10 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样例输出
0 1 4 4 6 7
-1 0 0 1 3 4
0 1 2 3 4 5样例解释
这正是教材 7.3 节的配送图（
| 轮次 | 确定 | 本轮生效的松弛 |
|---|---|---|
| 1 | 0 (0) | dist[1]=1，dist[2]=4，dist[5]=10 |
| 2 | 1 (1) | dist[3]=1+3=4（经 1→3） |
| 3 | 2 (4) | dist[4]=4+5=9（经 2→4）；2→3 需 5>4 不生效 |
| 4 | 3 (4) | dist[4]：9→6（改经 3→4）；3→5 需 10，与现状并列不生效 |
| 5 | 4 (6) | dist[5]：10→7（经 4→5，迟来的翻盘） |
| 6 | 5 (7) | 全部确定 |
注意第 3 轮：dist[2]=dist[3]=4 并列，按规则先确定编号小的 2。第 4 轮里 3→5 给出 4+6=10 与当前 dist[5]=10 并列，松弛不生效——若写成 <=，prev[5] 会被无意义地污染成 3。
任务
- 读入有向带权图（邻接表），读入源点
s； - 初始化
dist[s]=0，其余为无穷大标记；done[]全为假； - 循环
n次：选出未确定且dist最小（并列取编号最小）的顶点u；若选不出（剩余全部不可达）则提前结束； - 标记
done[u]=true，记录确定顺序；对u的每条出边(u,v,w)执行松弛：dist[u]+w < dist[v]时更新dist[v]与prev[v]； - 按输出格式打印三行（不可达以
-1表示）。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 部分顶点不可达 | dist 输出 -1，不参与确定顺序 |
| 零权边 | 正常参与松弛，0 权不等于无边 |
| 自环 | 松弛条件 dist[u]+w < dist[u] 对 w>=0 永不成立，自动无害 |
| 多重边 | 逐条松弛自然取更优者 |
| 单顶点图 | 只输出 0、-1 和 0 |
| 并列距离 | 编号最小者先确定，输出唯一 |
| 负权边 | 不属于自动评分输入（Dijkstra 前提被破坏，见 Lab 07-14） |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-07-dijkstra-trace
pnpm lab:run -- labs/chapter-07/exercise/E-07-07-dijkstra-trace
pnpm lab:score -- labs/chapter-07/exercise/E-07-07-dijkstra-trace完成清单
复杂度分析
外层循环 n 轮，每轮线性扫描选点 O(n)、松弛出边合计 O(m)，总计 O(n^2 + m)。这是考研手推与代码题的标准复杂度；当图稀疏（m << n^2）时堆优化到
思考与复盘
- 为什么"每轮选出的顶点，其
dist已是最终答案"不需要再修改？这一步在哪里用到了边权非负？
查看参考答案
设已确定集合为 S，本轮选出的 u 是 S 外暂定距离最小的顶点。若存在一条更短的 s→u 路径，它第一次离开 S 的边为 (x,y)；x 已确定，且因边权非负，s→x 的路径长度不超过整条 s→u 路径。松弛 (x,y) 后，y 的暂定距离就不会大于这条更短路径，从而不可能比 u 还大，和 u 的最小性矛盾。负边会让“前缀不超过全长”失效，因此这个证明不能成立。
- 若把平手规则改成"编号最大者优先"，
dist数组会变吗？哪一行输出会变？
查看参考答案
最短距离本身不变。第三行的确定顺序会改变；第二行的 prev 也可能改变：两条等长候选路径中，先被处理的前驱会先写入 prev，严格小于的松弛不会再覆盖它。因此不能只认为输出顺序会变。
- 朴素版与堆版在稠密图（
m ≈ n^2）上谁更快？为什么教材推荐稠密图用朴素版？
查看参考答案
稠密图上朴素版是
- 自环为什么不需要特判？若允许负权自环（
w < 0），会发生什么？
查看参考答案
对非负自环，dist[u] + w < dist[u] 永远不成立，严格松弛会自然忽略它。可达的负权自环则是负环，距离可以不断减小；它既破坏 Dijkstra 的前提，也没有有限最短路，应改用能检测负环的 Bellman-Ford。