NOI 竞赛模拟题：网络延迟时间

题目描述

在某个网络中，有 $n$ 个网络节点，标记为 $1$ 到 $n$。

给定一个列表 $times$，表示有向边的传递时间。$times[i] = (u_i, v_i, w_i)$，其中 $u_i$ 是源节点，$v_i$ 是目标节点，$w_i$ 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 $k$ 发出一个信号。我们需要计算：需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 $-1$。

---

输入格式

第一行包含三个整数 $n$，$m$ 和 $k$。$n$ 表示节点个数，$m$ 表示有向边的数量，$k$ 表示出发节点。 接下来 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 的有向边耗时为 $w_i$。

输出格式

输出一个整数，表示所有节点收到信号的最少时间。如果不可达，输出 $-1$。

---

输入输出样例

样例 1

输入：

4 3 2
2 1 1
2 3 1
3 4 1

输出：

2

样例 2

输入：

2 1 1
1 2 1

输出：

1

样例 3

输入：

2 1 2
1 2 1

输出：

-1

---

数据范围与提示

• $1 \le k \le n \le 100$
• $1 \le m \le 6000$
• $0 \le w_i \le 100$
• 所有 $(u_i, v_i)$ 对互不相同（无重边）。

---

1. 预备知识点

作为 NOI 选手，本题是图论中的“敲门砖”，涉及：

• 单源最短路 (SSSP)：核心目标是求从 $k$ 到其余所有点的最短距离中的最大值。
• Dijkstra 算法：最常用的最短路算法，配合优先队列（堆优化）效果更佳。
• 邻接表存储：使用 std::vector 或链式前向星处理稀疏图。
• 松弛操作 (Relaxation)：$dist(v) = min(dist(v), dist(u) + w)$。

---

2. 启发式思路引导（草稿纸上的推演）

第一步：理解“所有节点收到信号的时间”

• 信号从 $k$ 点出发，同时向所有邻居扩散。
• 某点 $v$ 收到信号的时间，就是从起点 $k$ 到 $v$ 的最短路径长度。
• “所有节点都收到”意味着我们需要求出每一个节点的最短路，然后取其中的最大值。

第二步：模型选择

• 边权全为正数吗？是的（$w_i \ge 0$）。
• 存在负环吗？不存在。
• 结论：这是标准的单源最短路问题。首选 Dijkstra 算法（稳健且快）。

第三步：算法流程

1. 初始化 dist 数组为无穷大（INF），dist[k] = 0。
2. 使用一个小根堆（优先队列）存储 {距离, 节点编号}。
3. 每次从堆顶取出距离最小且未访问的点 $u$。
4. 遍历 $u$ 的邻居 $v$，尝试松弛：如果经过 $u$ 到达 $v$ 的距离更短，更新 dist[v] 并入堆。
5. 遍历结束后，扫描 dist 数组。

第四步：特殊情况思考

• 如果扫描 dist 发现还有节点是 INF，说明该点不可达，输出 -1。
• 本题 $n=100$，规模极小，即使不用堆优化的 Dijkstra 甚至 Floyd 算法也能通过，但为了 NOI 规范，建议练习堆优化 Dijkstra。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 初始化距离数组 dist 等于 INF"] --> B["设置 dist 标记起始点 k 等于 0"]
    B --> C["建立小根堆 Q, 将一对 0 与 k 放入堆中"]
    C --> D{"堆 Q 是否为空?"}
    D -- "否" --> E["弹出堆顶最小距离项 (d, u)"]
    E --> F{"d 是否大于当前的 dist 标记 u?"}
    F -- "是 (失效数据)" --> D
    F -- "否" --> G["遍历 u 的所有出边 (u, v, w)"]
    G --> H{"dist 标记 u 加 w 是否小于 dist 标记 v?"}
    H -- "是 (松弛成功)" --> I["更新 dist 标记 v 等于 dist 标记 u 加 w"]
    I --> J["将新的一对 (dist 标记 v, v) 放入堆 Q"]
    J --> G
    H -- "否" --> G
    G -- "遍历邻居结束" --> D
    D -- "是" --> K["扫描所有 dist 标记"]
    K --> L{"是否存在 INF?"}
    L -- "是" --> M["输出 -1"]
    L -- "否" --> N["输出 dist 标记中的最大值"]
    M --> O["结束"]
    N --> O

---

4. 复杂度分析与优化建议

• 时间复杂度分析：
  • 堆优化 Dijkstra：每个节点入堆出堆各一次，每条边被松弛操作检查一次。复杂度为 $O(m \log m)$ 或 $O(m \log n)$。
  • 针对本题数据（$n=100, m=6000$）：$6000 \times \log(100) \approx 4 \times 10^4$，远低于 NOI 1秒 10^8 的限制。
• 空间复杂度分析：
  • 邻接表 $O(m)$，距离数组 $O(n)$，总复杂度 $O(n + m)$。
• 优化建议：
  • 在 $n$ 极小的情况下（如本题 $n \le 100$），也可以使用 Floyd-Warshall 算法（$O(n^3)$），代码更简洁，但要注意节点编号从 1 开始。
  • 在存在负权边（本题不涉及）时，应改用 SPFA 或 Bellman-Ford。

---

5. 读题关键词与坑点总结

1. “所有节点收到信号”：这是求“最短路中的最大值”的固定话术。
2. “不能使所有节点收到”：提示要检查连通性。
3. 节点编号：注意本题是 $1$ 到 $n$，数组开大一点（如 dist[105]）防止越界。
4. 单向边：注意是 u -> v 的有向图，建图时不要写成双向。
5. 边权为 0：Dijkstra 支持边权为 0，但不处理负权。若题目出现负权，需高度警惕。