从前往后删点, 删点不好做,那添加一个点呢?
从前往后枚举被删的点,枚举到 $i$ 时,他前面的点都被删了,后面的点都没被删,有什么启发呢?
诶~ 没错 从前往后删除点
不就相当于 从后往前添加点
,将一个点一个点加进来这不刚好就是 $floyd$?
做法就是:从后往前枚举所有被删除的点, 一个个点加进来, 求一下多源最短路就完事。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int p[N];
long long d[N][N], ans[N];
bool st[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> d[i][j];
for (int i = 1; i <= n; i ++ ) cin >> p[i];
for (int k = n; k; k -- ) {
int v = p[k];
st[v] = true;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][v] + d[v][j]);
long long sum = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (st[i] && st[j]) // 这两个点没被删
sum += d[i][j];
ans[k] = sum;
}
for (int i = 1; i <= n; i ++ ) cout << ans[i] << ' ';
return 0;
}
在atcoder写过类似的题目,主要是没懂题
%%%%%%
原来如此
腻害!
女少口阝可
%%%%%%%%%%%%%%%%%%%
妙啊,我一直想不到如何优化O(n^4)的暴力,原来是逆向思维
嘿嘿
泪目,没开longlong最后一个数据点没过
我也没开$wa$了一发
我也是
wcnmd比赛时写挂了,就差一点啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
哈哈哈哈
### 问一下佬
## 为什么不能改成:
### 超过k的点不是代表还没加进来吗,为什么要去更新它们之间的距离。
按次序加进来跟新其他点, 但其他的点至始至终都是存在的, 只是不会被没加进来的点更新
好的谢谢 提高课还没看到floyd