Description

题意：给定一个有向图，一共有N个点，给邻接矩阵。依次去掉N个节点，每一次去掉一个节点的同时，将其直接与当前节点相连的边和当前节点连出的边都需要去除，输出N个数，表示去掉当前节点之前的所有两点间最短距离和。n<=500

Solution

如果暴力打肯定是会超时的，那就要运用到floyd（hj）

floyd算法内2个循环就相当于新加入外循环的那个点然后跟新最短路，

所以可以把题目看成倒过来依次加点，每次\(n^2\)平方更新一下，总共\(O(n^3)\)

Code

#include <cstdio>

#include <algorithm>

#define ll long long

#define N 510

using namespace std;

ll Ans[N],g[N][N];

int p[N],n;

bool vis[N];

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%lld",&g[i][j]);

	for(int i=1;i<=n;++i)scanf("%d",&p[i]);

	for(int i=n,now;i>=1;--i){

		vis[now=p[i]]=1;

		for(int j=1;j<=n;++j)

			for(int k=1;k<=n;++k)

				g[j][k]=min(g[j][k],g[j][now]+g[now][k]);

		for(int j=1;j<=n;++j)

			for(int k=1;k<=n;++k)

				if(vis[j]&&vis[k]) Ans[i]+=g[j][k];

	}

	for(int i=1;i<=n;++i) printf("%lld ",Ans[i]);

	return 0;

}