← 返回题目列表

Codeforces · 2021/E1

E1. 数字村(简易版)

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

这是问题的简单版本。在这三个版本中,$$$n$$$ 和$$$m$$$ 的约束是不同的。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

Pak Chanek 正在为 Khuntien 村建立互联网连接。村庄可以表示为一个连接的简单图,其中包含 $$$n$$$ 房屋和 $$$m$$$ 连接房屋 $$$u_i$$$ 和房屋 $$$v_i$$$ 的互联网电缆,每个电缆的延迟为 $$$w_i$$$。

有 $$$p$$$ 房屋需要互联网。 Pak Chanek 最多可以在 $$$k$$$ 的房屋中安装服务器。然后,需要互联网的房屋将连接到其中一台服务器。然而,由于每条电缆都有其延迟,因此需要互联网的房屋 $$$s_i$$$ 经历的延迟将是该房屋与其所连接的服务器之间的电缆的最大延迟。

对于每个 $$$k = 1,2,\ldots,n$$$,帮助 Pak Chanek 确定所有需要互联网的房屋可以实现的最小总延迟。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$、$$$p$$$ ($$$2 \le n \le 400$$$; $$$n-1 \le m \le 400$$$; $$$1 \le p \le n$$$) — 房屋数量、电缆数量和需要互联网的房屋数量。

每个测试用例的第二行包含 $$$p$$$ 整数 $$$s_1, s_2, \ldots, s_p$$$ ($$$1 \le s_i \le n$$$) — 需要互联网的房屋。保证 $$$s$$$ 的所有元素都是不同的。

每个测试用例接下来的 $$$m$$$ 行的第 $$$i$$$ 行包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i < v_i \le n$$$; $$$1 \le w_i \le 10^9$$$) — 连接的互联网电缆房子 $$$u_i$$$ 和房子 $$$v_i$$$ 的延迟为 $$$w_i$$$。保证给定的边形成连通的简单图。

保证$$$n^3$$$之和与$$$m^3$$$之和不超过$$$10^8$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数:每个 $$$k = 1,2,\ldots,n$$$ 需要互联网的所有房屋可以实现的最小总延迟。

示例

输入 #1

2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2

输出 #1

34 19 9 4 0 0 0 0 0
2 0 0

注意

在 $$$k=3$$$ 的第一个测试用例中,可能的最佳解决方案是在顶点 $$$2$$$、$$$6$$$ 和 $$$8$$$ 处安装服务器,并获得以下延迟:

- $$$\text{延迟}(2) = 0$$$
- $$$\text{延迟}(5) = \max(3, 5) = 5$$$
- $$$\text{延迟}(6) = 0$$$
- $$$\text{延迟}(8) = 0$$$
- $$$\text{延迟}(9) = \max(2, 4) = 4$$$

因此总延迟为 $$$9$$$。