[AdditionalFile5605.zip](file://AdditionalFile5605.zip?type=additional_file)

#5605. 「JOI 2026 Semifinal」新桥

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Semifinal T5 「新たな橋 / New Bridge」

JOI 国是一个由 $N$ 个岛屿组成的国家，每个岛屿都有从 $1$ 到 $N$ 的编号。目前，该国还没有连接岛屿的桥梁，居民们的生活很不方便。

因此，作为 JOI 国大臣的你，决定作为国家项目新建桥梁。有 $M$ 个桥梁建设计划，第 $j$ $(1 \leq j \leq M)$ 个建设计划是花费 $C_{j}$ 的费用，在岛屿 $A_{j}$ 和岛屿 $B_{j}$ 之间架设一座双向通行的桥梁。这里，保证 $C_{1}, C_{2}, \ldots, C_{M}$ 互不相同。此外，保证在执行所有建设计划的情况下，所有岛屿都可以通过若干座桥梁相互到达。

由于 JOI 国的预算有限，你决定按如下方式实施国家项目：

1. 从 $N$ 个岛屿中选择一个岛屿 $s$，将其作为首都。
2. 进行 $N-1$ 次以下操作：
   • 在每次操作之前，将可以通过若干座桥梁从首都到达的岛屿称为近岛，否则称为远岛。在连接近岛和远岛的所有建设计划中，选择费用最低的一个并执行。
3. 在进行了 $N-1$ 次操作后，结束国家项目。

根据建设计划满足的约束条件，可以证明以下事实：

• 在每次操作中，一定存在可选的建设计划。此外，被执行的建设计划是唯一确定的。
• 当该项目结束时，所有岛屿都可以通过若干座桥梁相互到达。

正在考虑移居 JOI 国的凛，为了参考住在哪个岛屿，决定按如下方式计算各岛屿的不便度。岛屿 $i$ $(1 \leq i \leq N)$ 的不便度定义如下：

• 设 $D_{s, i}$ 为：当以岛屿 $s$ $(1 \leq s \leq N)$ 作为首都实施国家项目时，直到岛屿 $i$ 变得可以从首都到达为止，所执行的建设计划的数量。这里，当 $s=i$ 时，$D_{s, i}$ 为 $0$。
• 岛屿 $i$ 的不便度是所有 $1 \leq s \leq N$ 对应的 $D_{s, i}$ 的总和。

凛想计算作为搬家候选地的 $Q$ 个岛屿 $X_{1}, X_{2}, \ldots, X_{Q}$ 的不便度。给定建设计划和搬家候选岛屿的信息，请编写一个程序求出这些岛屿的不便度。

输入格式

第一行包含三个用空格分隔的整数 $N,M,Q$。

接下来 $M$ 行，每行包含三个用空格分隔的整数 $A_i, B_i, C_i$ $(1\leq i\leq M)$。

接下来 $Q$ 行，每行包含一个整数 $X_j$ $(1\leq j\leq Q)$。

输出格式

输出 $Q$ 行。在第 $k$ 行，输出岛屿 $X_{k}$ $(1 \leq k \leq Q)$ 的不便度。

样例 1

输入

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

输出

7
3

例如，考虑以岛屿 $1$ 为首都实施国家项目的情况。此时，建设计划将按如下方式执行：

1. 执行第 $1$ 个建设计划。首都将可以新到达岛屿 $3$。
2. 执行第 $3$ 个建设计划。首都将可以新到达岛屿 $2$。
3. 执行第 $5$ 个建设计划。首都将可以新到达岛屿 $4$。

综上所述，$D_{1,1}=0, D_{1,2}=2, D_{1,3}=1, D_{1,4}=3$。

因为 $D_{2,1}=2, D_{3,1}=2, D_{4,1}=3$，所以岛屿 1 的不便度为 $D_{1,1}+D_{2,1}+D_{3,1}+D_{4,1}=0+2+2+3=7$。

此外，因为 $D_{2,3}=1, D_{3,3}=0, D_{4,3}=1$，所以岛屿 3 的不便度为 $D_{1,3}+D_{2,3}+D_{3,3}+D_{4,3}=1+1+0+1=3$。

此样例满足子任务 $1, 2, 6$ 的限制。

样例 2

输入

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

输出

12
8
7
10
13

此样例满足子任务 $1, 2, 4, 6$ 的限制。

样例 3

输入

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

输出

43

此样例满足子任务 $1, 2, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 300000$
• $1 \leq M \leq 600000$
• $1 \leq Q \leq N$
• $1 \leq A_{j} < B_{j} \leq N$ $(1 \leq j \leq M)$
• 在执行所有建设计划的情况下，所有岛屿都可以通过若干座桥梁相互到达。
• $1 \leq C_{j} \leq 10^{9}$ $(1 \leq j \leq M)$
• $C_{1}, C_{2}, \ldots, C_{M}$ 互不相同。
• $1 \leq X_{k} \leq N$ $(1 \leq k \leq Q)$
• $X_{1}, X_{2}, \ldots, X_{Q}$ 互不相同。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$5$	$N \leq 2000, M \leq 2000$
$2$	$8$	$N \leq 2000$
$3$	$9$	$M=N-1, A_{j}=j, B_{j}=j+1$ $(1 \leq j \leq M), Q=1$
$4$	$18$	$M=N-1, A_{j}=j, B_{j}=j+1$ $(1 \leq j \leq M)$
$5$	$28$	$Q=1$
$6$	$32$	无附加限制