ALGORITHM NOTES阅读地图
7个主要章节
1段代码示例
6组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览7 节 · 展开选择

删掉一个顶点，经过它的最短路可能全部失效。仅从原来的最短距离里减去一些数，并不能找回绕行路线。若所有删除顺序提前给出，就可以反过来问：每次加入一个顶点，哪些路径第一次变得可用？

这篇承接 Dijkstra 的路径代价与动态规划的状态定义，把 Floyd 的外层循环解释成“逐个放开中间点”。这里不是在线维护任意增删图，而是利用已经知道的完整操作顺序。

官方题目与朴素代价

295B · Greg and Graph 的官方难度为 1700，标签为 dp、graphs、shortest paths。输入是完全有向图的邻接矩阵，1≤n≤500，非对角边权 1…100000，对角为零；两个方向的权重可以不同。删除序列是顶点的一个排列。每次删除之前，输出当前所有有序点对的最短距离之和。元信息及范围核对于 2026-10-21。

如果对每个剩余图重新运行 Floyd，总时间为 O(n⁴)。若只保存最初的全图距离，删除后又无法知道最短路是否偷偷使用了已经消失的点。难点是限制路径的内部顶点，而非只限制求和的端点。

反转操作，先明确允许什么

删除顺序记为 x₁,…,xₙ。逆序依次加入 xₙ,…,x₁；当刚加入 xₜ 时，活动点集合恰好等于正序第 t 次删除之前的剩余集合。

定义 d[i][j]：从 i 到 j、内部顶点只允许取自已加入集合 S 的最短距离。i、j 本身可以尚未加入。端点与内部顶点是两种不同权限。

端点一尚未加入，中间点二已加入，端点三尚未加入；一到三仍应提前由十更新为二加三等于五。
原创状态图，数字取自下文自拟矩阵。未激活端点的距离也要更新；只有内部顶点需要已激活。查看原图

初始 S 为空，没有内部顶点，故 d=a。加入 k 后，对所有 i、j 执行：

d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

更新完成后，只对 i、j 都在 S 中的有序点对求和。对角项为零，包含它们也不影响结果。

为什么一次松弛足够

归纳假设：加入 k 前，所有 d[i][j] 都已是内部顶点限制在 S 的最优距离。

加入 k 后，最短路径分两类：不经过 k 时，旧距离已经最优；经过 k 时，因为权重为正，可以去掉环并取一条简单最短路径，k 只出现一次。将路径在 k 切开，两段内部顶点都在旧 S 内，因此代价至少为旧 d[i][k]+d[k][j]。反过来，两段最短路拼接给出可行行走，若有重复顶点可去环，不会增加代价。所以两类取最小恰好得到新状态。

原地更新也成立：d[k][k]=0 且无负环，经过 k 不会让第 k 行或第 k 列变得更短。因此本轮使用的 d[i][k]、d[k][j] 保持旧值，等价于分层转移。k 必须是最外层循环；i、j 的先后可交换。

这个不变量覆盖未激活端点。等到一个端点真正加入时，它已经积累了此前所有中间点的路径信息，无需补做旧层。

三个顶点的完整手算

自拟矩阵如下，行是起点、列是终点：

a 1 2 3
1 0 2 10
2 8 0 3
3 4 9 0

删除顺序为 [1,3,2]，加入顺序是 [2,3,1]。

加入点活动集合本轮发生的缩短活动有序点对距离和答案位置
2{2}d₁₃：10→2+3=50第 3 项
3{2,3}d₂₁：8→3+4=73+9=12第 2 项
1{1,2,3}d₃₂：9→4+2=62+5+7+3+4+6=27第 1 项

输出为 27 12 0。第二项的 3→2 距离仍是 9；路径 3→1→2 虽然只花 6，但那时点 1 已经被删除，不能使用。

为什么不能只更新活动端点

上例首次加入 2 时，1 与 3 都未激活，却必须把 d[1][3] 从 10 更新到 5。若跳过它，之后加入 3 时仍拿着旧的 10；同样还会漏掉经由 3 对 d[2][1] 的更新。最后加入 1 的转移只能尝试经由 1，无法重新补上错过的中间点，最终错误得到总和 33。

自检：为何最终全图距离不能直接用于中间答案？

最终距离可能经过尚未加入的中间点。例子里最终 d₃₂=6，但只剩 {2,3} 时应为 9。端点存在并不表示路径内部点存在。

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& value : row) cin >> value;
    vector<int> x(n);
    for (int& v : x) { cin >> v; --v; }
    vector<bool> active(n, false);
    vector<long long> answer(n);
    for (int t = n - 1; t >= 0; --t) {
        int k = x[t];
        active[k] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
        long long sum = 0;
        for (int i = 0; i < n; ++i) if (active[i]) {
            for (int j = 0; j < n; ++j) if (active[j]) sum += d[i][j];
        }
        answer[t] = sum;
    }
    for (int t = 0; t < n; ++t) {
        if (t) cout << ' ';
        cout << answer[t];
    }
    cout << '\n';
}

每轮一次 n² 松弛和至多 n² 求和，共 O(n³) 时间，矩阵 O(n²) 空间。完全图保证两点间总有直接边，所以有限距离不超过 100000，代码无需无穷大哨兵；有序点对之和可达 500×499×100000=24950000000，必须用 long long。这里连矩阵也统一用 64 位，便于安全相加。

边界与验证

检查 应有行为 常见错误
n=1 唯一答案为 0 漏掉最后单点状态
非对称边权 两个方向分别计算 擅自把矩阵对称化
删除前求和 加入 xₜ 后存 answer[t] 少算一个顶点
尚未加入的端点 仍然参与距离更新 只更新活动端点
500 个点、最大权重 总和 24950000000 使用 int 累加
任意在线删除 本文方法不直接适用 忽略离线前提

验证程序 tests/verify-reverse-floyd-article.cjs 提取正文代码实际编译，用每个正序剩余图上重新运行的逐源稠密 Dijkstra 独立核对全部答案；同时检查上面的手算与“只更新活动端点”反例、单点、非对称、全部删除排列的小图和 n=500 的 64 位边界。测试覆盖的范围以程序实际输出为准。

继续比较 0-1 BFS：它利用边权限制加速单源搜索；本题则利用操作顺序，让全点对动态规划只增加状态权限。二者节省工作的依据不同。