【问题描述】
给定一张n个点的有向带权完全图，和一个数组a[]，请按顺序删除数组中的点，请求出删除点a[i]之前，所有未删除点对之间的最短路上的值的和。
【输入格式】
第一行一个整数n，表示点数；
接下来n行，每行n个数构成邻接矩阵，描述每条边的权值，保证i号点到i号点的权值为0；
最后一行n个小于等于n的不同的数，描述数组a[]
【输出格式】
输出1行n个数，表示答案。
【输入样例】
4
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³，更新的时候也只考虑用与它相连的点的最优解来更新其它距离。
下面是代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#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; } |
.jpg)