← 返回题目列表

AtCoder · arc035_c

C. Atcoder王国的交通情况

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

問題文

高桥先生是Atcoder王国的国王。他统治的Atcoder王国, 编号至1 如果要将其更改为输出最多为 N 编号最多为 N 具有双向访问连接的城市 M 由一条主干道组成。每条路都有长度。 Atcoder 王国中城市的任意组合 关于 (A,B) , 沿着A 的一些道路行驶 保证您可以达到 B 。

高桥先生认为,Atcoder人民的幸福很大程度上取决于交通的便利程度。 为了了解人们的幸福程度,我们计算了所有可能城市之间的最短路线长度的总和。 我想找到 S 。

都市 i 和 将其放在 j 之间的最短路径长度是 D(i,j) 如果 它表示为 S 是 当

。

高桥先生还参与公共工程。K 我正在考虑修建一条新路。 这项建设创造了一条直接连接某些城市的道路。 2 可能有不止一条道路,在这种情况下,我们将添加新道路而不是拆除现有道路。

你的工作是按照给定的顺序建造新道路,每次建造时,你 目的是编写一个程序来计算 S 。


入力

输入将以以下形式通过标准输入给出。

N M
A_1 B_1 C_1
A_2 B_2 C_2
:
A_M B_M C_M
K
X_1 Y_1 Z_1
:
X_K Y_K Z_K
  • 1 城市和道路的数量显示在第二行。 2 整数 编写一个程序来查找 N (1 ≦ N ≦ 400) 和 将其放在 M (1 ≦M ≦ 1000) 用空格分隔。
  • 2 来自行 M 行提供有关现有道路的信息。这几天之一 代表第 i (1≦i≦M) 行中,i 路的信息 3 整数 编写一个程序来查找 A_i(1≦A_i≦N)、 B_i(1≦B_i≦N)、 C_i(1≦C_i≦1,000) 用空格分隔。这是i 第条路是城市 A_i 和 将其放在 B_i 距离 表示它们与 C_i连接。A_i≠B_i ,直接连接同一城市的道路最多。 1 一。
  • 城市的任意组合 保证可以到达 (A,B) , 沿着A 的一些道路行驶 保证您可以达到 B 。
  • 2+M 第二行显示了新建道路的数量。 写入 K (1≦K≦400) 。
  • 3+M 来自行 K 行提供有关新建道路的信息。这几天之一 代表有关 i (1≦i≦K) 行中,i 条新道路的信息 3 整数 编写一个程序来查找 X_i(1≦X_i≦N)、 Y_i(1≦Y_i≦N)、 Z_i(1≦Z_i≦1,000) 以空格分隔。i 城市新路 代表与 X_i 和 将其放在 Y_i 距离 表示它们与 Z_i 连接。X_i≠Y_i 。

出力

应按以下格式输出到标准输出。 新道路建成后所有可能城市之间的最短路线长度之和,直至

i (1≦i≦K) 行中,i 新建道路后所有可能城市之间的最短路线长度总和 S 。

不要忘记结尾的换行符。


入力例1

4 3
1 2 1
2 3 1
3 4 10
2
3 4 1
1 4 1

出力例1

10
8

初始状态如下。

第一次构建后,图表将如下所示:

第二次构建后,图表将如下所示:


入力例2

8 16
8 7 38
2 8 142
5 2 722
8 6 779
4 6 820
1 3 316
1 7 417
8 3 41
1 4 801
3 2 126
4 2 71
8 4 738
4 3 336
7 5 717
5 6 316
2 1 501
10
6 1 950
6 1 493
1 6 308
3 4 298
2 5 518
1 5 402
4 7 625
7 6 124
3 8 166
2 4 708

出力例2

13649
12878
11954
11954
11280
11058
11058
8099
8099
8099