Last Major City

题目描述

AtCoder 国由 $N$ 个城市和 $M$ 条连接它们的道路组成，并且可以通过经过若干道路在任意两座城市之间旅行。 城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。道路 $i$ 双向连接城市 $A_i$ 和 $B_i$。 由于国内交通日益增加，计划对一些道路进行扩建。 目前尚未扩建任何道路，扩建道路 $i$ 的费用为 $C_i$。 由于一次性扩建所有道路困难，计划先从 $N$ 个城市中指定 $K$ 个城市为 主要城市，并进行最少的必要扩建工作，使得可以仅通过已扩建的道路在任意两座主要城市之间旅行。 已经决定城市 $1, 2, \dots, K-1$ 将成为主要城市，但最后一个主要城市还未决定。 对于每个 $i=K, K+1, \dots, N$，回答以下问题：

如果将城市 $i$ 指定为最后一个主要城市，使得可以仅通过已扩建的道路在任意两座主要城市之间旅行，所需的扩建工作最低总费用是多少？

输入格式

输入按照下列格式从标准输入给出： $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$ 的问题的答案，作为一个整数。

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

3
6

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

84
82
56

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

85
64
94

提示

$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$ 可以通过经过若干道路在任意两座城市之间旅行。 所有输入值均为整数。 在上图中，带数字的圆圈表示具有这些编号的城市，带数字的线表示扩建费用为该数字的道路。 左图和右图分别对应 $i=3$ 和 $i=4$ 的情况。彩色圆圈表示主要城市，彩色粗线表示在最优解中被扩建的道路。

对于 $i=3$，扩建道路 $4$ 和 $5$ 的费用为 $2+1=3$，这是最小值。 对于 $i=4$，扩建道路 $1$、$4$ 和 $5$ 的费用为 $3+2+1=6$，这是最小值。
可能存在多条道路连接同一对城市。

标签: AtCoder|abc364G

来源

AtCoder|abc364G