分数: 400 分
问题陈述
高桥生活在一个由 N 城市。每个城市编号为 1 to N,以及城市人口 i is M_i.
有 K 这个国家的道路,以及道路 k 双向连接城市 U_k 和城市 V_k。高桥可以在由道路直接连接的两个城市之间双向行驶。他也可能多次经过同一条路或同一个城市。
高桥每次从城市出发 a 前往邻近城市 b 有公路直接相连,他必须支付通行费 M_a \times M_b.
高桥目前在城市 1。有 P 这个国家有机场的城市,分别是城市 E_1, E_2, \dots, E_P。一旦高桥到达任何有机场的城市,就可以离开该国。如果城市 1 本身有机场,他不用搬家就可以离开,总过路费是 0.
查找高桥从城市出发必须支付的最低总通行费 1 飞往任何有机场的城市。保证从city到至少一个有机场的城市 1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 2 \times 10^5
- 1 \leq P \leq N
- 1 \leq M_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq U_k < V_k \leq N (1 \leq k \leq K)
- 所有对 (U_k, V_k) 是不同的
- 1 \leq E_p \leq N (1 \leq p \leq P)
- E_1, E_2, \dots, E_P 都是不同的
- 从 城市 至少可到达一个拥有机场的城市 1 通过公路
- 所有输入值均为整数
输入
N K P M_1 M_2 \dots M_N U_1 V_1 U_2 V_2 \vdots U_K V_K E_1 E_2 \dots E_P
- 第一行包含城市数量 N, 道路数量 K,以及拥有机场的城市数量 P,用空格分隔。
- 第二行包含每个城市的人口 M_1, M_2, \dots, M_N,用空格分隔。
- 以下 K 线提供有关道路的信息。
- 的 (2 + k)第行 (1 \leq k \leq K) 包含有道路连接的两个城市的号码 k, U_k 和 V_k,用空格分隔。
- 的 (K + 3)- 第行包含有机场的城市编号 E_1, E_2, \dots, E_P,用空格分隔。
输出
在一行中打印高桥从城市出发必须支付的最低通行费总额 1 飞往任何有机场的城市。
示例输入 1
4 4 1 2 3 1 5 1 2 1 3 2 4 3 4 4
示例输出 1
7
示例输入 2
3 2 1 5 3 7 1 2 2 3 1
示例输出 2
0
示例输入 3
7 8 2 3 10 2 5 1 8 4 1 2 1 3 2 4 2 5 3 4 3 5 4 6 5 7 6 7
示例输出 3
12
示例输入 4
10 15 3 4 9 2 7 1 3 8 6 5 10 1 2 1 3 2 4 2 5 3 5 3 6 4 7 5 7 5 8 6 8 6 9 7 10 8 9 8 10 9 10 7 9 10
示例输出 4
18
示例输入 5
2 1 1 1 10000 1 2 2
示例输出 5
10000