Greg and Graph：原題鏈接

題意：

     給你一個(gè)有權(quán)有向圖，圖包含n個(gè)點(diǎn)，接下來(lái)會(huì)操作n次，逐漸刪除這n個(gè)點(diǎn)，并將與該點(diǎn)相關(guān)的所有邊刪除，求輸出操作之前圖中的所有最短路徑的和。

題目思路：

     通過(guò)題意求所有最短路徑的和，可得用Floyd算法去求解。本題主要難點(diǎn)在于如何去解決刪點(diǎn)并計(jì)算每個(gè)時(shí)段的最短路徑和。      為解決上述問(wèn)題，可以扭轉(zhuǎn)思維，將刪點(diǎn)該為加點(diǎn)的形式，完成Floyd的改變，核心代碼如下：

void floyd(){
	//將原先的刪除編號(hào)數(shù)組倒序輸出
	//改為對(duì)圖像進(jìn)行加點(diǎn) 
	for (int k=n;k>=1;k--)
	{
		//x為加的點(diǎn) 
		long long x=a[k];
		//利用vis記錄判斷點(diǎn)是否加入
		//標(biāo)記為1的點(diǎn)為以加入的點(diǎn) 
		vis[x]=1;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				//跳過(guò)i,j相等的情況 
				if (i==j)continue;
				//與能將所有點(diǎn)當(dāng)做跳板的原 Floyd算法不同
				//因?yàn)槲覀兪羌尤朦c(diǎn)，所以將加入的點(diǎn)當(dāng)做跳板，即滿足遍歷所有點(diǎn)，也完成加點(diǎn)，十分巧妙的構(gòu)思 
				mp[i][j]=min(mp[i][j],mp[i][x]+mp[x][j]);
				//只有當(dāng)i,j的編號(hào)加入圖后，才可以加入路徑和。
				//利用ans數(shù)組記錄每個(gè)時(shí)刻的路徑和 
				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(){
	//將原先的刪除編號(hào)數(shù)組倒序輸出
	//改為對(duì)圖像進(jìn)行加點(diǎn) 
	for (int k=n;k>=1;k--)
	{
		//x為加的點(diǎn) 
		long long x=a[k];
		//利用vis記錄判斷點(diǎn)是否加入
		//標(biāo)記為1的點(diǎn)為以加入的點(diǎn) 
		vis[x]=1;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				//跳過(guò)i,j相等的情況 
				if (i==j)continue;
				//與能將所有點(diǎn)當(dāng)做跳板的原 Floyd算法不同
				//因?yàn)閷⑽覀兪羌尤朦c(diǎn)，所以將加入的點(diǎn)當(dāng)做跳板，即滿足遍歷所有點(diǎn)，也完成加點(diǎn)，十分巧妙的構(gòu)思 
				mp[i][j]=min(mp[i][j],mp[i][x]+mp[x][j]);
				//只有當(dāng)i,j的編號(hào)加入圖后，才可以加入路徑和。
				//利用ans數(shù)組記錄每個(gè)時(shí)刻的路徑和 
				if (vis[i] && vis[j])ans[k]+=mp[i][j];
			}
		}
	}
	return ;
}


int main(){
	cin >>n;
	//讀入各點(diǎn) 
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)cin >>mp[i][j];
	}
    //讀入刪點(diǎn)編號(hào)
	for (int i=1;i<=n;i++)cin >>a[i];
	floyd();
	//雖然我們?cè)仁堑剐蜉斎?，但ans記錄的已經(jīng)是倒序時(shí)的路徑和，所以正序輸出即可 
	for (int i=1;i<=n;i++)cout <<ans[i]<<' ';
	cout <<"\n";
}