题解

思路

正向删除会使最短路失效，难以维护；反向看成按 $x_n,x_{n-1},\ldots,x_1$ 加入顶点。加入顶点 $k$ 后，它是唯一新增的可用中转点，因此一次 Floyd 松弛即可更新全部点对距离。

做法

初始距离为邻接矩阵。逆序枚举删除排列中的顶点 $k$，执行

（对所有 $i,j$）。然后只对已经加入的顶点集合求 $d_{ij}$ 之和，记录到对应的正向步骤。

正确性证明

归纳假设加入 $k$ 前，$d_{ij}$ 是只经过此前已加入顶点的最短路。加入 $k$ 后，任意新出现的更短简单路径经过 $k$ 至多一次，可拆成一条旧集合内从 $i$ 到 $k$ 的最短路和一条从 $k$ 到 $j$ 的最短路，因此 Floyd 转移恰好覆盖全部新最短路。归纳成立。每轮只累加当前已加入集合，正好对应正向删除该顶点之前的图，故所有输出正确。

复杂度分析

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。