Codeforces 25C Roads in Berland

首先给你一个带边权的有 n 个顶点的完全图，然后要在这个图上加 k 条边，求每次加边后，每两个顶点之间的最短路之和变成了多少，两个顶点是不考虑顺序的，也就是 a → b 的最短路和 b → a 的最短路只算一次。

原题地址：http://codeforces.com/problemset/problem/25/C

数据范围是 2 ≤ n ≤ 300, 1 ≤ k ≤ 300.

输入数据第一行是 n, 第二行开始是一个 n × n 的矩阵，表示图。之后一行是 k, 表示要插入几条边，之后 k 行表示边连接的点和边权值。

输出数据只有一行，就是每加入一条边后，最短路的总和变成了多少。

输入数据 1:

2
0 5
5 0
1
1 2 3

输出数据 1:

3

输入数据 2:

3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1

输出数据 2:

17 12

这个嘛，我的感觉就是首先先计算总的最短路的和。然后每加入一条边的时候，先判断加的边是不是使得最短路更短了，如果不是的话直接输出那个和就可以了；如果是的话，就枚举顶点对：比如加的边是 (u, v), 枚举顶点对 (x, y), 看看原先 x 到 y 的最短路和 x → u → v → y 的最短路哪个比较短，短的话就松弛，并且记录差值。最后把原先计算的和减掉所有差值的和就可以得到结果了。