Couti 厌倦了繁琐的作业,所以他打开了他多年前创建的一个旧编程问题。
给你一个连通的无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 加权边。有 $$$k$$$ 特殊顶点:$$$x_1、x_2、\ldots、x_k$$$。
让我们将路径的成本定义为路径中边的最大权重。两个顶点之间的距离作为连接它们的路径的最小成本。
对于每个特殊顶点,找到距它最远的另一个特殊顶点(就上一段而言,即对应的距离是最大可能的)并输出它们之间的距离。
原来的约束很小,所以他觉得这个问题很无聊。现在他提出了约束条件,希望你能帮他解决。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \leq k \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 10^5$$$) — 顶点数、边数和特殊顶点数。
第二行包含 $$$k$$$ 不同的整数 $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \leq x_i \leq n$$$)。
以下 $$$m$$$ 行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ ($$$1 \leq u,v \leq n, 1 \leq w \leq 10^9$$$),表示权重 $$$u$$$ 和 $$$v$$$ 之间有一条边$$$w$$$。给定的图是无向的,因此边 $$$(u, v)$$$ 可以在两个方向上使用。
该图可能具有多条边和自环。
保证图是连通的。
输出
第一行也是唯一一行应包含 $$$k$$$ 整数。第 $$$i$$$ 个整数是 $$$x_i$$$ 与距离它最远的特殊顶点之间的距离。
示例
输入 #1
2 3 2 2 1 1 2 3 1 2 2 2 2 1
输出 #1
2 2
输入 #2
4 5 3 1 2 3 1 2 5 4 2 1 2 3 2 1 4 4 1 3 3
输出 #2
3 3 3
注意
在第一个示例中,顶点 $$$1$$$ 和 $$$2$$$ 之间的距离等于 $$$2$$$,因为人们可以穿过连接它们的权重 $$$2$$$ 的边缘。因此 $$$1$$$ 和 $$$2$$$ 到最远节点的距离都等于 $$$2$$$。
在第二个例子中,可以发现$$$1$$$和$$$2$$$之间的距离,$$$1$$$和$$$3$$$之间的距离都是$$$3$$$,$$$2$$$和$$$3$$$之间的距离是$$$2$$$。
该图可能具有多条边和自循环,如第一个示例中所示。