Greg and Graph：原题链接

题意：

     给你一个有权有向图，图包含n个点，接下来会操作n次，逐渐删除这n个点，并将与该点相关的所有边删除，求输出操作之前图中的所有最短路径的和。

题目思路：

     通过题意求所有最短路径的和，可得用Floyd算法去求解。本题主要难点在于如何去解决删点并计算每个时段的最短路径和。      为解决上述问题，可以扭转思维，将删点该为加点的形式，完成Floyd的改变，核心代码如下：

void floyd(){
	//将原先的删除编号数组倒序输出
	//改为对图像进行加点 
	for (int k=n;k>=1;k--)
	{
		//x为加的点 
		long long x=a[k];
		//利用vis记录判断点是否加入
		//标记为1的点为以加入的点 
		vis[x]=1;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				//跳过i,j相等的情况 
				if (i==j)continue;
				//与能将所有点当做跳板的原 Floyd算法不同
				//因为我们是加入点，所以将加入的点当做跳板，即满足遍历所有点，也完成加点，十分巧妙的构思 
				mp[i][j]=min(mp[i][j],mp[i][x]+mp[x][j]);
				//只有当i,j的编号加入图后，才可以加入路径和。
				//利用ans数组记录每个时刻的路径和 
				if (vis[i] && vis[j])ans[k]+=mp[i][j];
			}
		}
	}
	return ;
}

     在理解完核心代码后，基本就能得出AC代码了。

     以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1e3,inf=0x3f3f3f3f;
long long n;
long long a[N*N],vis[N*N],ans[N*N],mp[N][N];

void floyd(){
	//将原先的删除编号数组倒序输出
	//改为对图像进行加点 
	for (int k=n;k>=1;k--)
	{
		//x为加的点 
		long long x=a[k];
		//利用vis记录判断点是否加入
		//标记为1的点为以加入的点 
		vis[x]=1;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				//跳过i,j相等的情况 
				if (i==j)continue;
				//与能将所有点当做跳板的原 Floyd算法不同
				//因为将我们是加入点，所以将加入的点当做跳板，即满足遍历所有点，也完成加点，十分巧妙的构思 
				mp[i][j]=min(mp[i][j],mp[i][x]+mp[x][j]);
				//只有当i,j的编号加入图后，才可以加入路径和。
				//利用ans数组记录每个时刻的路径和 
				if (vis[i] && vis[j])ans[k]+=mp[i][j];
			}
		}
	}
	return ;
}


int main(){
	cin >>n;
	//读入各点 
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)cin >>mp[i][j];
	}
    //读入删点编号
	for (int i=1;i<=n;i++)cin >>a[i];
	floyd();
	//虽然我们原先是倒序输入，但ans记录的已经是倒序时的路径和，所以正序输出即可 
	for (int i=1;i<=n;i++)cout <<ans[i]<<' ';
	cout <<"\n";
}