← 返回题目列表

AtCoder · awc0089_d

D. 最便宜的路线

中文机器翻译题面 查看原题

分数: 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