学习目标

• 能写出 Floyd 的三重循环并解释为什么 k 必须最外层；
• 能解释在无负环前提下，为什么可以用二维数组原地保存三维 DP 的当前阶段；
• 能用 nxt 后继矩阵还原任意点对的完整路径；
• 能把 Floyd 与"重复 n 次 Dijkstra"做复杂度对比，并说明各自适用场景。

前置知识

先读第 7.4 节最短路径的"第三幕 · 全源：Floyd 的动态规划"。本题把教材的"运费表"落地成可查询的导航服务——灵感来自南中医"校园最短路径"实验：按地图建图，回答任意两点间的路线。

核心思想：按"允许的中转点"递推

Floyd 的状态是 $d^{(k)}(i,j)$：只允许顶点 $0..k$ 充当中转时，$i\to j$ 的最短距离。递推式按"路径是否经过顶点 $k$"分类：

$$d^{(k)}(i,j)=min(d^{(k-1)}(i,j),d^{(k-1)}(i,k)+d^{(k-1)}(k,j)).$$

为什么 k 必须在最外层：第 $k$ 轮要求"只经前 $k-1$ 个中转"的所有最短路都已备齐。把 k 放进内层会同一轮里混用新旧状态，某些需要依次接力中转的路径会算错（教材练习 4 有完整反例）。

为什么二维数组够：无负环时 $d(k,k)=0$。第 $k$ 轮中，经 $k$ 更新 $d(i,k)$ 的候选仍为 $d(i,k)+d(k,k)=d(i,k)$，因此第 $k$ 列不会变化；第 $k$ 行同理。原地更新时读取到的这两部分仍是上一阶段的值，所以不必保存完整的三维数组。

后继矩阵 nxt：路径还原的关键

nxt[i][j] 记录"从 i 出发到 j 的最短路上，第一步走到哪"。

• 初始化：i == j 或无边时 -1；有边时 nxt[i][j] = j；
• 松弛生效（d[i][k] + d[k][j] < d[i][j]）时：nxt[i][j] = nxt[i][k]——改经 k 中转后，i 迈出的第一步是"i 通往 k 的路"的第一步，不是 k 本身。

还原路径：从 u = s 出发，输出 u，令 u = nxt[u][t]，直到 u == t。若 nxt[s][t] == -1 则不可达。

输入格式

第一行三个整数 n m q：顶点数、有向边数、查询数。

接下来 m 行，每行三个整数 u v w，表示 u -> v 的有向边，边权 w 可以为负。

接下来 q 行，每行两个整数 s t，表示一次查询：从 s 到 t 的最短路径。

输入保证：

• 1 <= n <= 300；
• 0 <= m <= 2*10^5；
• 0 <= u, v < n（允许自环与多重边；多重边取最小权，非负自环不改变已初始化的 d[i][i]=0）；
• -10^4 <= w <= 10^4；
• 图中不含负环（负权边允许）；
• 1 <= q <= 1000。
• 每次查询满足 0 <= s, t < n。

输出格式

对每次查询输出一行：

• 可达：dist: v0 v1 ... vk（v0 = s，vk = t）；
• 不可达：-1；
• s == t：0: s。

样例输入

6 10 3
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 5
2 5
5 0

样例输出

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

样例解释

教材配送图。0→5 最短路 $A\to B\to D\to E\to F$ 权 $7$；2→5 是 $C\to D\to E\to F$ 权 $4$；5→0 不可达（F 没有出边）。三问答案与教材最终矩阵 $D^{(6)}$ 逐一对应。

任务

1. 读入边表构造邻接矩阵 d（无边 INF，对角线 0），同时初始化 nxt；
2. 三重循环跑 Floyd（k 外层），更新 d 与 nxt；
3. 对每个查询，判可达、输出距离与路径。

正常、边界与错误情况

情况	预期行为
负权边（无负环）	正常计算，结果有效
不可达点对	输出 -1
s == t	输出 0: s
多重边	邻接矩阵取最小权
自环	非负自环不改变 d[i][i]=0；负自环属于负环，与输入保证冲突
多条等长路径	nxt 由严格小于的更新规则唯一确定
稀疏大图	Floyd 依然 $O(n^3)$，n=300 约 $2.7\times {10}^7$ 次内层操作，时限内可过

运行与评分

在本 Lab 目录执行：

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

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

pnpm lab:doctor -- labs/chapter-07/exercise/E-07-20-floyd-all-pairs
pnpm lab:run -- labs/chapter-07/exercise/E-07-20-floyd-all-pairs
pnpm lab:score -- labs/chapter-07/exercise/E-07-20-floyd-all-pairs

完成清单

• 全部测试用例通过；
• k 在最外层，i/j 顺序任意；
• nxt 更新写 nxt[i][j] = nxt[i][k] 而非 = k；
• 松弛用严格小于，INF 参与加法前先判有限；
• s == t 与不可达两类边界正确处理。

解题思路

令 dist[i][j] 表示当前点对最短距离，依次把每个顶点作为中转点。若经过 k 更短就更新距离，并同步更新后继矩阵，查询时沿后继逐步还原路径。

复杂度分析

时间 $O(n^3)$，空间 $O(n^2)$。与"重复 $n$ 次 Dijkstra"相比：非负权稠密图下后者 $O(n^3)$ 同阶但常数更大；负权图下后者根本不可用。Floyd 的定位是顶点数少、要全部点对、可能含负边——先看 7.3 节选型表再动手。

思考与复盘

1. 为什么 nxt[i][j] = nxt[i][k] 而不是 nxt[i][j] = k？用样例中 0→5 的路径逐轮验证。

查看参考答案

经 k 更新 i→j 后，路径是“先走 i→k 的最短路，再走 k→j 的最短路”，所以第一步必须沿用 nxt[i][k]。例如样例最终把 0→5 经顶点 4 更新时，真正路径是 0→1→3→4→5，第一步是 1；若写成 4，还原会错误地假定存在直边 0→4。

2. 若图含负环，Floyd 跑完会发现什么？对角线有什么特征？（提示：回顾 7.3 节负环探测器）

查看参考答案

能从某顶点出发并回到它的负环会使该顶点的自到自距离小于零，因此出现 d[i][i] < 0。能够到达并离开该负环的点对没有有限最短距离，路径还原也不再具有题目所要求的语义，所以本题输入明确排除负环。

3. 与"无向图跑 Floyd"相比，本题的有向图多了哪些不可达组合？路径输出格式一致吗？

查看参考答案

有向图中 u→v 可达并不推出 v→u 可达，单向链、汇点和不同方向的强连通分量之间都会产生更多不可达点对。无向图把每条边双向写入后，同一连通分量内任意点对都可达。两种图的输出格式完全一致，仍是距离加从源点到目标点的顶点序列。

4. 若 q 次查询改用"每次跑一遍 Dijkstra"，什么图下反而更划算？

查看参考答案

在边权非负、图很稀疏且查询数 q 远小于 n 时，逐次 Dijkstra 的 $O(q(n+m)\log n)$ 可能远小于 Floyd 的 $O(n^3)$，也不必预计算从未查询的点对。若存在负边则不能直接使用 Dijkstra；若图稠密或查询接近全部点对，Floyd 通常更合适。