CF1081D Maximum Distance

Chouti 厌倦了枯燥的作业，于是他打开了几年前自己出的一个老编程题。 给定一个包含 $n$ 个顶点和 $m$ 条带权边的连通无向图。有 $k$ 个特殊顶点：$x_1, x_2, \ldots, x_k$。 我们定义一条路径的代价为该路径上所有边权的最大值。两个顶点之间的距离为连接它们的所有路径中代价的最小值。 对于每一个特殊顶点，找出另一个距离它最远的特殊顶点（即上述定义下距离最大的那个），并输出它们之间的距离。 原本的限制很小，所以 Chouti 觉得这题很无聊。现在，他提高了限制，希望你能帮他解决这个问题。

第一行包含三个整数 $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$ 之间的距离为 $2$，因为可以通过权值为 $2$ 的边直接相连。因此对于 $1$ 和 $2$，距离最远的特殊顶点的距离都是 $2$。 在第二个样例中，可以发现 $1$ 和 $2$ 之间的距离、$1$ 和 $3$ 之间的距离都是 $3$，$2$ 和 $3$ 之间的距离是 $2$。 图中可能存在重边和自环，如第一个样例所示。 由 ChatGPT 4.1 翻译