D - Cheapest Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は N 個の都市からなる国に住んでいます。各都市には 1 から N までの番号が付けられており、都市 i の人口は M_i です。

この国には K 本の道路が整備されており、道路 k は都市 U_k と都市 V_k を双方向に結んでいます。高橋君は道路で直接結ばれた2つの都市の間を、どちらの方向にも移動することができます。また、同じ道路や同じ都市を複数回通ることもできます。

高橋君が道路で直接結ばれた都市 a から隣接する都市 b へ1回移動するごとに、通行料として M_a \times M_b を支払わなければなりません。

高橋君は現在、都市 1 にいます。この国には P 個の空港のある都市があり、それらは都市 E_1, E_2, \dots, E_P です。高橋君はいずれかの空港のある都市にたどり着けば、この国から出国することができます。都市 1 自体が空港のある都市である場合は、移動せずに出国でき、通行料の合計は 0 です。

高橋君が都市 1 から出発し、いずれかの空港のある都市に到達するまでに支払う通行料の合計の最小値を求めてください。なお、都市 1 から少なくとも 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 から少なくとも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
  • 1 行目には、都市の数 N 、道路の数 K 、空港のある都市の数 P が、スペース区切りで与えられる。
  • 2 行目には、各都市の人口 M_1, M_2, \dots, M_N が、スペース区切りで与えられる。
  • 続く K 行にわたり、道路の情報が与えられる。
  • 2 + k 行目 (1 \leq k \leq K) には、道路 k が結ぶ2つの都市の番号 U_k と V_k が、スペース区切りで与えられる。
  • K + 3 行目には、空港のある都市の番号 E_1, E_2, \dots, E_P が、スペース区切りで与えられる。

出力

高橋君が都市 1 からいずれかの空港のある都市に到達するまでに支払う通行料の合計の最小値を 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

Score : 400 pts

Problem Statement

Takahashi lives in a country consisting of N cities. Each city is numbered from 1 to N, and the population of city i is M_i.

There are K roads in this country, and road k bidirectionally connects city U_k and city V_k. Takahashi can travel in either direction between two cities that are directly connected by a road. He may also pass through the same road or the same city multiple times.

Each time Takahashi travels from city a to an adjacent city b that is directly connected by a road, he must pay a toll of M_a \times M_b.

Takahashi is currently in city 1. There are P cities with airports in this country, which are cities E_1, E_2, \dots, E_P. Takahashi can leave the country once he reaches any city with an airport. If city 1 itself has an airport, he can leave without moving, and the total toll is 0.

Find the minimum total toll Takahashi must pay to travel from city 1 to any city with an airport. It is guaranteed that at least one city with an airport is reachable from city 1.

Constraints

  • 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)
  • All pairs (U_k, V_k) are distinct
  • 1 \leq E_p \leq N (1 \leq p \leq P)
  • E_1, E_2, \dots, E_P are all distinct
  • At least one city with an airport is reachable from city 1 via roads
  • All input values are integers

Input

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
  • The first line contains the number of cities N, the number of roads K, and the number of cities with airports P, separated by spaces.
  • The second line contains the population of each city M_1, M_2, \dots, M_N, separated by spaces.
  • The following K lines provide information about the roads.
  • The (2 + k)-th line (1 \leq k \leq K) contains the numbers of the two cities connected by road k, U_k and V_k, separated by spaces.
  • The (K + 3)-th line contains the numbers of the cities with airports E_1, E_2, \dots, E_P, separated by spaces.

Output

Print in one line the minimum total toll Takahashi must pay to travel from city 1 to any city with an airport.

Sample Input 1

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

Sample Output 1

7

Sample Input 2

3 2 1
5 3 7
1 2
2 3
1

Sample Output 2

0

Sample Input 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

Sample Output 3

12

Sample Input 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

Sample Output 4

18

Sample Input 5

2 1 1
1 10000
1 2
2

Sample Output 5

10000