这是问题的困难版本。在这三个版本中,$$$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 2000$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$、$$$p$$$ ($$$2 \le n \le 5000$$$; $$$n-1 \le m \le 5000$$$; $$$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$$$和$$$m$$$的总和不超过$$$5000$$$。
输出
对于每个测试用例,输出 $$$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$$$。