【Shortest】

2015年10月23日 0条评论 695次阅读 0人点赞

【问题描述】

给定一张n个点的有向带权完全图，和一个数组a[]，请按顺序删除数组中的点，请求出删除点a[i]之前，所有未删除点对之间的最短路上的值的和。

【输入格式】

第一行一个整数n，表示点数；

接下来n行，每行n个数构成邻接矩阵，描述每条边的权值，保证i号点到i号点的权值为0；

最后一行n个小于等于n的不同的数，描述数组a[]

【输出格式】

输出1行n个数，表示答案。

【输入样例】

0 3 1 1

6 0 400 1

2 4 0 1

1 1 1 0

4 1 2 3

【输出样例】

17 23 404 0

【数据范围】

对30%的输入数据：1≤n≤10

对100%的输入数据：1≤n≤500，权值≤100000

Floyed新技能get

正向思考很难，可以考虑逆向加点。对于每次加一个点，考虑从它出发的边能否更新旁边的点，把与它有关的所有边都扫一次进行更新。之后再跑一遍Floyed来更新整个图，时间复杂度为n³，更新的时候也只考虑用与它相连的点的最优解来更新其它距离。

下面是代码:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#define M 501
#define ll long long
using namespace std;
int n,map[M][M],del[M];
ll dis[M][M],ans[M];
bool flag[M];
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	//freopen("shortest.in","r",stdin);
	//freopen("shortest.out","w",stdout);
	memset(dis,40,sizeof(dis));
	n=read();
	for(int i=1;i<=n;i++) 
	 for(int j=1;j<=n;j++)
	  map[i][j]=read();
	for(int i=1;i<=n;i++) del[i]=read();
	for(int i=n;i>=1;i--)
	{
		flag[del[i]]=true;
		dis[del[i]][del[i]]=0;
		for(int j=1;j<=n;j++)
		 for(int k=1;k<=n;k++)
		 {
		 	if(!flag[j]||!flag[k]) continue;
		 	dis[j][del[i]]=min(dis[j][del[i]],dis[j][k]+map[k][del[i]]);
		 	dis[del[i]][j]=min(dis[del[i]][j],map[del[i]][k]+dis[k][j]);
		 }
		ans[i]=0;
	    for(int j=1;j<=n;j++)
	     for(int k=1;k<=n;k++)
	     {
	     	if(!flag[j]||!flag[k]) continue;
	     	dis[j][k]=min(dis[j][k],dis[j][del[i]]+dis[del[i]][k]);
	     	ans[i]+=dis[j][k];
		 }
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}