K站中转内最便宜的航班

题目描述

有 $n$ 座城市，城市编号从 $0$ 到 $n-1$。城市之间通过一些航班连接。给定一个数组 flights，其中 $flights[i] = [from_i, to_i, price_i]$，表示该航班从城市 $from_i$ 出发，以价格 $price_i$ 抵达 $to_i$。

现在给定所有的城市和航班信息，以及出发城市 src 和目的地 dst。你的任务是找到一条最多经过 $k$ 站中转的路线，使得从 src 到 dst 的价格最便宜。

如果不存在这样的路线，则输出 -1。

词义解释：最多经过 $k$ 站中转，意味着从起点到终点最多可以经过 $k+1$ 条边。

---

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$。$m$ 为航班数量。 接下来 $m$ 行，每行三个整数 $u_i$、$v_i$、$w_i$，表示从 $u_i$ 到 $v_i$ 的航班价格为 $w_i$。 最后一行包含两个整数 $src$ 和 $dst$。

输出格式

输出一个整数，表示符合中转限制的最便宜价格。如果不可达，输出 -1。

---

输入输出样例

样例 1

输入：

4 5 1
0 1 100
1 2 100
2 0 100
1 3 600
2 3 200
0 3

输出：

700

解释： 从城市 0 到城市 3 最多中转 1 站的最佳路径为 0 -> 1 -> 3，费用为 100 + 600 = 700。 注意 0 -> 1 -> 2 -> 3 路径虽然只需 400，但中转了 2 站，不符合要求。

样例 2

输入：

3 3 1
0 1 100
1 2 100
0 2 500
0 2

输出：

200

样例 3

输入：

3 3 0
0 1 100
1 2 100
0 2 500
0 2

输出：

500

---

数据范围与提示

• $2 \le n \le 100$
• $0 \le m \le n(n-1)/2$
• $1 \le price_i \le 10^4$
• $0 \le k < n$
• 所有城市对之间最多只有一班飞机，且无自环。

---

1. 预备知识点

作为 NOI 选手，处理此类“步数限制最短路”需掌握：

• 动态规划 (DP)：具有明显阶段性的决策问题。
• Bellman-Ford 算法：天然支持“限制边数”的最短路。
• 分层图思想：将“步数”作为图的一个维度（层）。
• 数组拷贝与滚动优化：防止在同一轮迭代中发生多次松弛。

---

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

第一步：识别核心矛盾

• 普通最短路（如 Dijkstra）优先保证价格最便宜。
• 冲突点：有的路径很便宜但步数多，有的路径贵但步数少。
• 启发：我们必须在状态中强制加入“步数”或“次数”这一维度。

第二步：确定状态转移

• 设 $f[i][v]$ 表示经过恰好 $i$ 次飞行到达城市 $v$ 的最小花费。
• $i$ 的范围是从 $1$ 到 $k+1$。
• 转移：$f[i][v] = \min(f[i-1][u] + cost(u, v))$。

第三步：空间优化思考

• 观察发现，$f[i]$ 的状态只依赖于 $f[i-1]$。
• 结论：可以使用两个一维数组 dist 和 last 交替更新，类似于 Bellman-Ford 的每轮松弛。

第四步：防止“超前松弛”

• 如果在同一轮循环中，你用更新过的 $v$ 去更新 $w$，那么在一轮中你就走了两步。
• 对策：在每一轮开始前，先备份上一轮的 dist 数组为 last，只用 last 的数据去更新 dist。

---

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

graph TD
    A["开始: 初始化距离数组 dist"] --> B["设置 dist 全部为 INF, 且 dist(src) = 0"]
    B --> C["外层循环: t 从 0 遍历到 k"]
    C --> D{"t 小于等于 k?"}
    D -- "是" --> E["拷贝 dist 拷贝到备份数组 last"]
    E --> F["内层循环: 遍历每一条航班 (u, v, price)"]
    F --> G{"last(u) 是否小于 INF?"}
    G -- "是" --> H["尝试松弛: dist(v) = min(dist(v), last(u) + price)"]
    G -- "否" --> I["跳过此边"]
    H --> F
    I --> F
    F -- "所有边遍历完" --> C
    D -- "否" --> J{"dist(dst) 是否仍为 INF?"}
    J -- "是" --> K["输出 -1"]
    J -- "否" --> L["输出 dist(dst)"]
    K --> M["结束"]
    L --> M

---

4. 读题关键词与复杂度分析

读题关键词：

1. “最多经过 k 站中转”：意味着最多有 $k+1$ 条边。在 Bellman-Ford 中，这对应 $k+1$ 次松弛操作。
2. “最便宜”：单源最短路代价。
3. “$n \le 100$”：数据范围极小。这意味着即使是 $O(K \cdot M)$ 的算法也能在几毫秒内跑完。

复杂度分析过程：

• 时间复杂度：
  • 进行 $k+1$ 轮迭代。
  • 每轮迭代遍历 $m$ 条边。
  • 总复杂度 $O(k \cdot m)$。
  • 代入最大值：$100 \times 5000 = 5 \times 10^5$，远低于 NOI 1秒 10^8 的限制。
• 空间复杂度：
  • 只需要两个长度为 $n$ 的数组。
  • 复杂度 $O(n)$。

时间复杂度优化建议：

• 虽然 $k \cdot m$ 已经很快，但在某些极端稠密图中，如果 dist 数组在某次迭代后不再变化，可以提前退出。
• 但由于本题有“恰好 $k$ 步”的逻辑暗示（其实是最多），使用副本数组 last 是最稳健的做法。

5. 易错点总结

• INF 的设置：1e4 * 100 最大价格约 $10^6$，不要把 INF 设得太小。
• 备份数组：如果不备份就松弛，程序会跑出不受中转次数限制的普通最短路，导致样例 1 输出 400 而不是 700。