← 返回题目列表

AtCoder · abc364_g

G. 最后一个主要城市

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

分数: 600 点

问题陈述

AtCoder 的国家/地区包括 N 城市和 M 道路将它们连接起来,通过某些道路就可以在任意两个城市之间行驶。 城市编号从 1 to N,道路编号从 1 to M。道路 i 连接城市 A_i 和 B_i 双向。

由于该国交通量不断增加,计划扩建一些道路。 目前尚未扩建道路,扩建道路的费用 i is C_i.

由于很难一次性扩建所有道路,因此计划首先指定 K 出 N 城市为 主要城市 并执行最低限度的必要扩建工程,以便人们可以仅使用扩建后的道路在任何两个主要城市之间行驶。 已经决定各城市 1, 2, \dots, K-1 将是主要城市,但最后一个主要城市尚未确定。

对于每个 i=K, K+1, \dots, N,回答以下问题:

  • 如果城市 i 被指定为最后一个主要城市,为确保人们可以仅使用扩建后的道路在任意两个主要城市之间出行,所需扩建工程的最低总成本是多少?

约束

  • 2 \leq N \leq 4000
  • N-1 \leq M \leq 8000
  • 2\leq K \leq \min(N,\,10)
  • 1 \leq A_i < B_i \leq N
  • 1 \leq C_i \leq 10^9
  • 通过穿越一些道路,可以在任意两个城市之间旅行。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M K
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

输出

打印 N-K+1 行。 的 l第行 (1 \leq l \leq N-K+1) 应包含问题的答案 i=l+K-1,作为整数。


示例输入 1

4 5 3
1 4 3
3 4 4
1 2 4
2 3 2
1 3 1

示例输出 1

3
6

上图中,带数字的圆圈代表该数字的城市,带数字的线代表道路,扩建成本就是该数字。 左右图对应案例 分别为 i=3 和 i=4。彩色圆圈代表主要城市,彩色粗线代表最优解中扩展的道路。

  • 对于 i=3, 扩建道路 4 和 5 导致总成本为 2+1=3,这是最小值。
  • 对于 i=4, 扩建道路 1, 4,和 5 导致总成本为 3+2+1=6,这是最小值。

示例输入 2

4 3 2
2 4 28
1 4 56
1 3 82

示例输出 2

84
82
56

示例输入 3

6 12 4
2 6 68
2 5 93
4 6 28
2 4 89
3 6 31
1 3 10
1 2 53
3 5 1
3 5 74
3 4 22
4 5 80
3 4 35

示例输出 3

85
64
94

可能有多条道路连接同一对城市。