题意：给你一个完全图，给你删点顺序，问你这些点删除前 整个图的最短路的和。
解题思路：这其实是floyd-warshall 算法的 一个应用。我们可以从最后一个点开始 ，对他的顺序进行映射，题意就正好符合floyd 的定义。
解题代码：
1 // File Name: 295b.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月11日 星期三 19时13分13秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 LL dp[505][505]; 28 int de[505]; 29 int hs[505]; 30 int tmp[505][505]; 31 LL ans[505]; 32 int main(){ 33 int n ; 34 scanf("%d",&n); 35 for(int i = 1;i <= n;i ++) 36 { 37 for(int j= 1;j <= n ;j ++) 38 scanf("%d",&tmp[i][j]); 39 } 40 for(int i = 1;i <= n;i ++) 41 scanf("%d",&de[i]); 42 for(int i = n ;i >= 1;i --) 43 { 44 hs[n-i+1] = de[i]; 45 } 46 for(int i= 1;i <= n;i ++) 47 { 48 for(int j = 1;j <= n; j ++) 49 { 50 dp[i][j] = tmp[hs[i]][hs[j]]; 51 } 52 } 53 54 for(int k = 1; k <= n;k ++) 55 { 56 for(int i = 1;i <= n;i ++) 57 { 58 for(int j = 1;j <= n;j ++) 59 { 60 dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]); 61 // printf("%I64d ",dp[i][j]); 62 } 63 // printf(" "); 64 } 65 LL sum = 0 ; 66 for(int i = 1;i <= k; i ++) 67 { 68 for(int j = 1;j <= k;j ++) 69 { 70 sum += dp[i][j]; 71 } 72 } 73 ans[k] = sum; 74 } 75 for(int i =n;i >=1; i --) 76 { 77 printf("%I64d ",ans[i]); 78 } 79 printf(" "); 80 81 return 0; 82 }