题意

本题要求理解并应用弗洛伊德（Floyd）算法的核心原理。题目中给出的是标准的弗洛伊德算法实现，通过三重循环逐步更新任意两点之间的最短路径。

思路

弗洛伊德算法的通用形式如下：

for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

即在每一步中，我们尝试通过顶点 $k$ 来“中转”路径。
本题的思路不是删除顶点，而是逆向添加顶点（从后往前处理）。
在每一步中，我们尝试通过新加入的顶点，在所有顶点之间进行路径中转。
这样可以得到一个时间复杂度为 $O(n^3)$ 的解法。

算法步骤

1. 初始化距离矩阵 $a$，其中 $a[i][j]$ 表示顶点 $i$ 到顶点 $j$ 的当前最短距离。
2. 按照逆向顺序（从最后一个顶点到第一个顶点）依次添加顶点。
3. 每添加一个顶点 $k$，就使用该顶点作为中转点，更新所有顶点对 $(i, j)$ 的距离：
   • $a[i][j] = \min(a[i][j], a[i][k] + a[k][j])$
4. 重复步骤 3，直到所有顶点都被添加完毕。

复杂度分析

• 时间复杂度：$O(n^3)$，因为三重循环分别遍历所有顶点对和中转顶点。
• 空间复杂度：$O(n^2)$，用于存储距离矩阵。

代码说明

代码实现的核心是三重循环，其中外层循环 $k$ 表示当前添加的顶点，内层循环 $i$ 和 $j$ 遍历所有顶点对。每次通过 $k$ 进行松弛操作，更新最短路径。由于是逆向添加顶点，最终得到的结果与正向删除顶点等价。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n;
int dis[505][505];
int d[505];
int ansline[505],book[505];
signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++)
		cin >> dis[i][j];
	for(int i = 1 ; i <= n ; i ++)cin >> d[i];
	for(int v = n ; v >= 1 ; v --){
		int x = d[v];
		book[x] = 1;
		for (int i = 1 ; i <= n ; i ++)
			for (int j = 1 ; j <= n ; j ++)
			if(i != j){
            //因为把当前加入的点x作为中转点，所以我们去掉了一重循环
				dis[i][j] = min(dis[i][x] + dis[x][j],dis[i][j]);//x即是当前加入的点
				if(book[i] != 0 && book[j] != 0)ansline[v] += dis[i][j];
			}
	}
	for(int i = 1 ; i <= n ; i ++)cout << ansline[i] <<" ";
	return 0;
}