← 返回题目列表

Codeforces · 25/C

C. 贝尔兰的道路

中文机器翻译题面 查看原题

Berland有n个城市,编号从1到n。其中一些由双向道路连接。每条道路都有自己的长度——从 1 到 1000 的整数。众所周知,从每个城市都可以通过现有道路到达任何其他城市。此外,对于每对城市,它们之间的最短距离也是已知的。柏林政府计划修建 k 条新道路。对于每条规划的道路,其长度以及将连接哪些城市都是已知的。为了控制新道路建设的正确性,在另一条道路开通后,贝尔兰政府希望检查所有成对城市之间的最短距离之和。帮助他们——对于给定的旧道路上的最短距离矩阵和所有新道路的规划,找出每条道路建设后所有对城市之间的最短距离之和如何变化。

输入

第一行包含整数 n (2 ≤ n ≤ 300) — Berland 的城市数量。接下来是 n 行,每行有 n 个整数——最短距离矩阵。第 i 行中的第 j 个整数 — di, j,城市 i 和 j 之间的最短距离。保证 di, i = 0, di, j = dj, i,并且给定的矩阵是一组长度为 1 到 1000 整数的双向道路的最短距离矩阵,这样从每个城市都可以使用这些道路到达任何其他城市。

下一行包含整数 k (1 ≤ k ≤ 300) — 规划道路的数量。接下来的 k 行包含了规划道路的描述。每条道路由三个空格分隔的整数 ai、bi、ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1000) 描述 - ai 和 bi - 道路连接的城市对,ci - 道路的长度。两个城市之间可以是多条道路,但没有一条道路将城市与其本身连接起来。

输出

输出 k 个空格分隔的整数 qi (1 ≤ i ≤ k)。 qi 应等于指数为 1 至 i 的道路建设后所有对城市之间的最短距离之和。道路按照输入顺序从 1 开始编号。每对城市应在总和中考虑一次,即。 e.我们计算无序对。

示例

输入 #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