https://www.luogu.com.cn/problem/CF295B?contestId=180677
Greg 有一个有边权的有向图，包含 n 个点。这个图的每两个点之间都有两个方向的边。Greg 喜欢用他的图玩游戏，现在他发明了一种新游戏：
游戏包含 n 步。第 i 步 Greg 从图中删掉编号为 xi的点。当删除一个点时，这个点的出边和入边都会被删除。在执行每一步之前，Greg 想知道所有点对间最短路长度的和。
最短路可以经过任何没删掉的点。换句话说，如果我们假设 (,,)d(i,v,u) 是在删掉 xi 前 v 和 u 间的最短路长度，那么Greg想知道下面这个求和的值：∑,,≠(,,)∑ v,u,v=u
d(i,v,u) 。帮帮 Greg，输出每一步之前要求的值。
题意大概
正常按题意来讲是根据先算出一个点走向所有点的最小值后再删除一个点算出除了那一个点后的走过所有点的最小值,一次类推将一个个点删除后除了这些点以后的最小值
但无疑这样子写对我们而言十分困难去写他，所以我们用逆向思维先将所有点的点删除，然后删除的点进行倒叙得到一个新的顺序根据这个新的顺序我们将我们的点一个个加回来
一个个进行计算并将他们倒叙进行存储下面献上代码
思路
将题目的所有点进行删除，我们相当于在空白的纸上，从后往前将删除的点恢复并用floyd进行计算最小值
并进行记录
点击查看代码
`#include<bits/stdc++.h>
using namespace std;
long long dis[1000][1000],x[1000],vis[1000],judge[1000],ans[1000];//judge来判断该点是否被恢复 ,vis来记录删除的顺序
int main()
{
long long n;//记得开 long long 题目中给出提示
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 >> vis[i];
judge[vis[i]]=1;//将这些点进行删除
}
for(int i = n;i >=1; i--)
{
long long k = vis[i];//进行倒叙从后往前进行恢复
judge[vis[i]]=0;//将删除的最后一点-》1开始恢复
for(int j = 1; j <= n; j++)
{
for(int q = 1; q<= n; q++)
{
if(q==j)continue;//当出发点等于到达点时无意义所以跳过
dis[j][q]=min(dis[j][q],dis[j][k]+dis[k][q]); //计算起点到我要去的点的最小值。并将恢复的跳点进行对比，起点-》终点
//和起点-》到恢复的点-》终点的最小值进行对比取得最小值
if(judge[j]==0 && judge[q]==0)ans[i]+=dis[j][q];//判断上述最小值是否成立（这两个点是否已经恢复是否已经存在 ）将他存起来
}
}
}
for(int i=1;i<=n;i++)
{
cout << ans[i] <<" ";//答案要正序输出所以正常输出即可
}
return 0;
}`