/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
ある街には N 個の地点があり、1 から N まで番号が付けられています。地点間を結ぶ M 本の双方向の道があり、i 番目の道は地点 A_i と地点 B_i を結び、通過するのに C_i の時間がかかります。同じ 2 地点間に複数の道が存在することもあります。
高橋君はこの街で働く配達員です。毎日、配送センターである地点 1 を出発し、いくつかの届け先を回って地点 1 に戻ってきます。
今日は K 個の届け先 V_1, V_2, \ldots, V_K が指定されています(届け先に地点 1 は含まれません)。高橋君は地点 1 を出発し、K 個の届け先すべてに少なくとも 1 回ずつ訪れてから、地点 1 に戻らなければなりません。移動の途中で同じ地点や同じ道を何度通ってもよいですが、道を通過するたびにその道の所要時間が加算されます。
このような経路における所要時間の合計の最小値を求めてください。
制約
- 2 \leq N \leq 5 \times 10^4
- 1 \leq M \leq 5 \times 10^4
- 1 \leq K \leq 15
- 2 \leq V_i \leq N (1 \leq i \leq K)
- V_i はすべて異なる
- 1 \leq A_i, B_i \leq N, A_i \neq B_i (1 \leq i \leq M)
- 同じ 2 地点間に複数の道が存在することがある
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- すべての届け先は地点 1 から到達可能である
- 入力はすべて整数である
入力
N M K V_1 V_2 \ldots V_K A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
- 1 行目には、地点の数 N、道の数 M、届け先の数 K がスペース区切りで与えられる。
- 2 行目には、K 個の届け先の番号 V_1, V_2, \ldots, V_K がスペース区切りで与えられる。
- 続く M 行のうち i 行目 (1 \leq i \leq M) には、i 番目の道が結ぶ 2 つの地点 A_i, B_i と、その道の所要時間 C_i がスペース区切りで与えられる。
出力
地点 1 を出発し、K 個の届け先すべてに少なくとも 1 回ずつ訪れ、地点 1 に戻る経路について、所要時間の合計の最小値を 1 行で出力せよ。
入力例 1
4 5 2 2 3 1 2 2 2 3 3 3 1 4 1 4 10 4 3 1
出力例 1
9
入力例 2
5 8 2 3 5 1 2 1 2 3 1 1 3 10 1 3 3 1 4 2 4 5 2 3 5 100 2 5 5
出力例 2
12
入力例 3
8 12 3 4 6 8 1 2 2 2 3 2 3 4 2 1 5 3 5 6 3 6 7 3 7 8 3 4 8 4 2 5 2 3 6 2 4 7 2 1 8 20
出力例 3
22
入力例 4
14 22 5 4 7 9 12 14 1 2 4 2 3 3 3 4 5 4 5 2 5 6 4 6 7 3 7 8 6 8 9 2 9 10 4 10 11 3 11 12 5 12 13 2 13 14 4 1 5 7 2 6 6 4 8 5 5 9 8 7 11 4 9 13 3 3 10 12 6 12 9 1 14 30
出力例 4
51
入力例 5
16 15 15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 1 9 8 1 10 9 1 11 10 1 12 11 1 13 12 1 14 13 1 15 14 1 16 1000000000
出力例 5
2000000210
Score : 433 pts
Problem Statement
A city has N locations, numbered from 1 to N. There are M bidirectional roads connecting locations, where the i-th road connects location A_i and location B_i and takes C_i time to traverse. There may be multiple roads between the same pair of locations.
Takahashi is a delivery person working in this city. Every day, he departs from location 1, which is the distribution center, visits several delivery destinations, and returns to location 1.
Today, K delivery destinations V_1, V_2, \ldots, V_K have been specified (location 1 is not included among the destinations). Takahashi must depart from location 1, visit all K destinations at least once each, and then return to location 1. During his travel, he may pass through the same location or the same road any number of times, but each time he traverses a road, its travel time is added to the total.
Find the minimum total travel time of such a route.
Constraints
- 2 \leq N \leq 5 \times 10^4
- 1 \leq M \leq 5 \times 10^4
- 1 \leq K \leq 15
- 2 \leq V_i \leq N (1 \leq i \leq K)
- All V_i are distinct
- 1 \leq A_i, B_i \leq N, A_i \neq B_i (1 \leq i \leq M)
- There may be multiple roads between the same pair of locations
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- All destinations are reachable from location 1
- All input values are integers
Input
N M K V_1 V_2 \ldots V_K A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
- The first line contains the number of locations N, the number of roads M, and the number of destinations K, separated by spaces.
- The second line contains the K destination numbers V_1, V_2, \ldots, V_K, separated by spaces.
- The following M lines each contain, for the i-th line (1 \leq i \leq M), the two locations A_i, B_i connected by the i-th road and the travel time C_i of that road, separated by spaces.
Output
Print in one line the minimum total travel time of a route that departs from location 1, visits all K destinations at least once each, and returns to location 1.
Sample Input 1
4 5 2 2 3 1 2 2 2 3 3 3 1 4 1 4 10 4 3 1
Sample Output 1
9
Sample Input 2
5 8 2 3 5 1 2 1 2 3 1 1 3 10 1 3 3 1 4 2 4 5 2 3 5 100 2 5 5
Sample Output 2
12
Sample Input 3
8 12 3 4 6 8 1 2 2 2 3 2 3 4 2 1 5 3 5 6 3 6 7 3 7 8 3 4 8 4 2 5 2 3 6 2 4 7 2 1 8 20
Sample Output 3
22
Sample Input 4
14 22 5 4 7 9 12 14 1 2 4 2 3 3 3 4 5 4 5 2 5 6 4 6 7 3 7 8 6 8 9 2 9 10 4 10 11 3 11 12 5 12 13 2 13 14 4 1 5 7 2 6 6 4 8 5 5 9 8 7 11 4 9 13 3 3 10 12 6 12 9 1 14 30
Sample Output 4
51
Sample Input 5
16 15 15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 1 9 8 1 10 9 1 11 10 1 12 11 1 13 12 1 14 13 1 15 14 1 16 1000000000
Sample Output 5
2000000210