题目链接：
codeforces 295B
题目大意：
给出n个点的完全有权有向图，每次删去一个点，，求每次操作前整张图各个点的最短路之和。
题目分析：这样我们就知道了的递推中，最后一维其实标记的是作为媒介的点是前k个的情况，那么也就是我们之要1~k这些点组成图的最短路，那么因为在求取最短路时，并没有用后面的点作为媒介，所以就是我们要的答案，因为加入点无序，所以我们要先用hash将点对应到有序的序列上，然后直接利用floyd做就可以了，不懂的可以在评论中询问，我会耐心解答的。 AC代码：;LL;LL dp[MAX][MAX],ans[MAX],a[MAX][MAX];int n,x[MAX];map<int,int> mp;int main ( ){while (~scanf ( “%d” , &n )){mp.clear();for ( int i = 1 ; i <= n ; i++ )for ( int j = 1 ; j <= n ; j++ )scanf ( “%I64d” , &a[i][j] );for ( int i = 1 ; i <= n ; i++ ){scanf ( “%d” , &x[i] );mp[x[i]] = n+1-i;}for ( int i = 1 ; i <= n ; i++ )for ( int j = 1 ; j <= n ; j++ )dp[mp[i]][mp[j]] = a[i][j];for ( int k = 1; k <= n ; k++ ){for ( int i = 1 ; i <= n ; i++ )for ( int j = 1 ; j <= n ; j++ )dp[i][j] = min ( dp[i][j] , dp[i][k] + dp[k][j] );for ( int i = 1 ; i <= k; i++ )for ( int j = 1 ; j <= k; j++ )ans[n-k+1] += dp[i][j];}for ( int i = 1 ; i <= n ; i++ )printf ( “%I64d ” , ans[i] );puts (“”);}}
如果寒暄只是打个招呼就了事的话，那与猴子的呼叫声有什么不同呢?事实上，
