• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

本题的难点在想到正难则反的思路， 还有对floyd的理解。

题目大意

给出一个有权有向图（实际上是一个完全图），每一次删掉一个点，求删掉点之前的最短路之和。
$1\leq n\leq 500$

思路

首先肯定能想到floyd，但是 $\mathcal{O}(n^4)$ 的暴力时间复杂度是不能够接受的。考虑优化。之后考虑正难则反的解题思路。因为可以从样例中发现最后一个都是 $0$，然后往前推就又发现了多出来的一个正好是最短路，然后再往前推。

如果可以想到这一步的话答案就出来了。每一次我们把最后一个删除的点加回来，一开始图是空的。之后用这个点为中转 $k$ 去求当前的全源最短路。之后枚举每两个点，如果两个点都在新图里，那么就加上这两个点之间的最短路长度。时间复杂度 $\mathcal{O}(n^3)$，可以通过。

注意，floyd的外层中转点是没有顺序要求的，只要都遍历一遍就可以了。因为早晚都要遍历一遍。如果刻板的去思考从 $1$ 开始单调递增的floyd模版对解决本题是没有丝毫帮助的。

代码

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAXN = 505;
ll dp[MAXN][MAXN], x[MAXN], n, ans[MAXN];
bool add[MAXN];

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%lld", &dp[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &x[i]);
    }
    for (ll k = n; k >= 1; --k) {
        add[x[k]] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = min(dp[i][j], dp[i][x[k]] + dp[x[k]][j]);
            }
        }
        ll sum = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (add[i] && add[j]) {
                    sum += dp[i][j];
                }
            }
        }
        ans[k] = sum;
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    return 0;
}

总结

本题可以极好的帮助理解floyd和锻炼思路。首先一个点就在于正难则反，这个点的训练方法为不断地去模拟样例，不只是根据一个思路，如果一片空白的话就要从不同的角度去反复折磨（开个玩笑😁）样例，不断地去观察其中的规律。

一定要在一开始找到一个方向。还有一个帮助思考的技巧在于将一个复杂的题面转化成一个简单好看的题面。这可以帮助我们从感性上理解一道题变成从理性的角度去分析。比如本题就可以转化成上面的题意，看起来就比一些包装的无意义字符好理解多了。不一定要绝对严谨，自己能看懂同时不会出现思维误区即可。