学习目标
前置知识
完成 Lab 07-10。本题是堆版 Dijkstra 的一句话变体：Dijkstra 求出 dist 后，答案就是
题目背景
网络中有 n 个节点，标号 0..n-1。一条有向边 u v w 表示信号从 u 发出、经 w 毫秒到达 v。现在节点 s 发出一个信号，信号沿边传播是并行的——每个节点收到后立刻沿自己的所有出边转发。
问：所有节点都收到信号需要多少毫秒？ 若有节点永远收不到，输出 -1。
关键转化：每个节点收到信号的最早时刻就是 dist[i]（单源最短距离）。所有节点收齐的时刻是这些最短距离的最大值；存在不可达节点则无解。
输入格式
第一行三个整数 n m s，分别表示节点数、有向边数与源点编号。
接下来 m 行，每行三个整数 u v w，表示 u -> v 的有向边，传播延迟 w 毫秒。
输入保证：
1 <= n <= 10^5；0 <= m <= 2*10^5；0 <= u, v < n；1 <= w <= 10^4；s为合法节点编号。
输出格式
一个整数：所有节点收齐信号所需的最短时间；若存在节点从 s 不可达，输出 -1。
样例输入
4 3 1
1 0 1
1 2 1
2 3 1样例输出
2样例解释
节点 1 在 0 时刻收信并转发；0 与 2 在 1 毫秒收信（同时），2 随即转发；3 在 2 毫秒收信。四个节点全部收到需要 2 毫秒。若移除边 2→3（保留节点 3），则 3 永远收不到，应输出 -1。
任务
- 读入有向带权图（邻接表）；
- 堆优化 Dijkstra 求
dist； - 取
max(dist[0..n-1])；若存在顶点dist == INF（不可达），输出-1；否则输出最大值。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 全部可达 | 输出最大最短距离 |
| 存在不可达节点 | 输出 -1 |
n == 1 | 源点即全部，输出 0 |
| 源点无出边 | 其余节点不可达，输出 -1 |
| 多重边 | 自然处理，保留更短者 |
| 稠密图 | 用堆版可能超时/超内存 → 换朴素版或注意边数上限 |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-09-network-delay-time
pnpm lab:run -- labs/chapter-07/exercise/E-07-09-network-delay-time
pnpm lab:score -- labs/chapter-07/exercise/E-07-09-network-delay-time完成清单
复杂度分析
堆优化 Dijkstra：n=10^5、m=2*10^5 是该实现的典型工作量级，也是 OJ 常规压力。
思考与复盘
- 信号传播是"并行"的，为什么答案仍是 Dijkstra 的
max dist而不是最短路径之和？
查看参考答案
每个节点收到信号后会立刻、同时向所有出边转发，各条路径没有排队关系。节点 v 的首次收到时间是从源点到它的最短路径长度；全网完成时间就是所有首次收到时间中最晚的一个，即 max dist。把距离相加会把并行传播错误地串行化。
- 本题与一般单源最短路的差别只有最后一步。为什么说"应用题的骨架永远是算法本身"？
查看参考答案
题目的叙事变成“信号到达”，但核心仍是同一张有向非负权图上的单源最短路。Dijkstra 负责求每个节点的最早到达时间；业务规则只是在结果上取最大值并处理不可达。先识别算法骨架，才能把不同题面稳定地转成代码。
- 若图变成无向图，答案会变化吗？复杂度会变化吗？
查看参考答案
无向边要拆成两条方向相反的边，新的可达性和最短距离可能使答案变小，原先不可达的图也可能变为可达。边数至多翻倍，渐近复杂度仍为
- 若希望输出"最晚收到信号的节点编号"（并列取最小），需要怎么改？
查看参考答案
完成 Dijkstra 后扫描所有 dist：发现更大的距离就更新答案；距离相等时取编号更小的节点。若扫描中发现不可达节点，仍应直接输出 -1，而不是给出一个“最晚节点”。