题目大意
给了一个 n(2<=n<=300) 个节点的无向图，告诉了每两个节点之间的最短距离，现在要新建 K(1<=K<=300) 条边
要求：每建一条边，输出任意两个点之间最短的距离的和
做法分析
首先，如果直接暴力的话肯定 T(因为是 o(n4) 的时间复杂度)
我们需要注意的是，每次只是新建一条边
令 g[i][j] 表示顶点 i 和顶点 j 之间的最短距离
假设新建的边是 a---b 边权为 c
如果 g[a][b]<=c 那么，新建的边不会用来更新多有顶点之间的最短距离，这时候直接统计最短距离和输出就行，下面讨论 g[a][b]>c 的情况
首先 g[a][b]=g[b][a]=c 这是肯定的了
由于只是新加了边，原来图中的边还存在（虽然我们不知道这些边的具体情况），那么我们可以这么做，还是利用 Floyd 算法的思想
先求出 a 到其他所有点的最短距离 g[i][a] (由于 g[a][i]=g[i][a]，我们只讨论一种情况)
g[i][a] 要么不经过 a---b 这条边，要么经过这条边，于是很好解决了：
g[i][a]=g[a][i]=min( g[i][a], g[i][b]+g[b][a] )
同理，求出 b 到其他所有的点的最短距离：
g[i][b]=g[b][i]=min( g[i][b], g[i][a]+g[a][b] )
最后，对于任意两个点 i 和 j，他们的最短路，要么经过 a，要么经过 b，要么还是原来的值，那么
g[i][j]=min(g[i][j], min(g[i][a]+g[a][j], g[i][b]+g[b][j]) )
这样，任意两个点之间的最短路就求出来了，然后暴力统计就行了
参考代码
C. Roads in Berland
1 #include <cstring> 2 #include <cstdio> 3 #include <iostream> 4 5 using namespace std; 6 7 const int N=3006; 8 long long g[N][N]; 9 int n, m; 10 11 int main() 12 { 13 scanf("%d", &n); 14 for(int i=1; i<=n; i++) 15 for(int j=1; j<=n; j++) 16 scanf("%I64d", &g[i][j]); 17 scanf("%d", &m); 18 for(int e=0, a, b, c; e<m; e++) 19 { 20 scanf("%d%d%d", &a, &b, &c); 21 if(g[a][b]>c) 22 { 23 g[a][b]=g[b][a]=c; 24 25 for(int k=1; k<=n; k++) 26 for(int i=1; i<=n; i++) 27 g[i][a]=g[a][i]=min(g[a][i], g[a][b]+g[b][i]); 28 for(int k=1; k<=n; k++) 29 for(int i=1; i<=n; i++) 30 g[i][b]=g[b][i]=min(g[b][i], g[b][a]+g[a][i]); 31 for(int i=1; i<=n; i++) 32 for(int j=i+1; j<=n; j++) 33 { 34 g[i][j]=g[j][i]=min(g[i][j], g[i][a]+g[a][j]); 35 g[i][j]=g[j][i]=min(g[i][j], g[i][b]+g[b][j]); 36 } 37 } 38 long long sum=0; 39 for(int i=1; i<=n; i++) 40 for(int j=i+1; j<=n; j++) 41 sum+=g[i][j]; 42 printf("%I64d\n", sum); 43 } 44 }