E - 宅配ドライバーの巡回 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は宅配ドライバーとして働いており、毎日お客様のもとへ荷物を届けています。

高橋君が担当するエリアは N 個の交差点と M 本の道路からなっています。交差点には 1 から N までの番号が付けられています。 i 番目 (1 \leq i \leq M) の道路は交差点 U_i と交差点 V_i を双方向に結んでおり、どちらの方向に通過しても W_i 分かかります。同じ 2 つの交差点を結ぶ道路が複数存在することもあります。

今日は K 件の配達依頼があり、 j 番目 (1 \leq j \leq K) の依頼では交差点 D_j にいるお客様に荷物を届ける必要があります。 K 件の配達先の交差点はすべて異なり、いずれも営業所のある交差点 S とは異なります。高橋君は営業所のある交差点 S から出発し、 K 件すべての配達先を訪れた後、再び交差点 S に戻ってこなければなりません。配達先を訪れる順番は自由に決めることができます。また、移動の途中で同じ交差点や同じ道路を何度通ってもかまいません。

ある配達先への配達は、移動経路の途中であっても、その交差点を通った時点で自動的に完了するものとします。すなわち、ある配達先に向かう途中で別の配達先を経由した場合、その配達先への配達も完了します。荷物の受け渡しにかかる時間は考えないものとします。

すべての配達を終えて営業所に戻るまでの最小の合計移動時間（分）を求めてください。

なお、交差点 S からすべての配達先へ到達可能であることが保証されます（道路は双方向なので、各配達先から交差点 S に戻ることも可能です）。

制約

  • 2 \leq N \leq 10\,000
  • 1 \leq M \leq 20\,000
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • 1 \leq S \leq N
  • 1 \leq K \leq 15
  • 1 \leq D_j \leq N
  • D_j はすべて異なる
  • D_j \neq S
  • すべての配達先へ S から到達可能である
  • 入力はすべて整数である

入力

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
S K
D_1 D_2 \ldots D_K
  • 1 行目には、交差点の数 N と道路の数 M がスペース区切りで与えられる。
  • 続く M 行の i 行目 (1 \leq i \leq M) には、 i 番目の道路が結ぶ 2 つの交差点の番号 U_i, V_i と、通過にかかる時間 W_i （分）がスペース区切りで与えられる。
  • 次の行には、営業所のある交差点の番号 S と配達件数 K がスペース区切りで与えられる。
  • 次の行には、 K 個の配達先の交差点番号 D_1, D_2, \ldots, D_K がスペース区切りで与えられる。

出力

すべての配達先を訪れて営業所に戻るまでの最小の合計移動時間（分）を整数で 1 行に出力せよ。

入力例 1

4 5
1 2 2
2 3 3
3 4 4
1 4 7
1 3 10
1 2
3 4

出力例 1

16

入力例 2

6 8
1 2 3
1 3 5
2 3 1
2 4 7
3 5 4
4 5 2
4 6 3
5 6 6
1 3
4 5 6

出力例 2

26

入力例 3

10 14
1 2 5
1 3 12
2 3 4
2 4 8
3 5 3
4 5 6
4 6 2
5 7 7
6 7 4
6 8 9
7 9 3
8 9 5
8 10 2
9 10 6
1 5
3 5 7 9 10

出力例 3

54

Score : 433 pts

Problem Statement

Takahashi works as a delivery driver, delivering packages to customers every day.

The area Takahashi is responsible for consists of N intersections and M roads. The intersections are numbered from 1 to N. The i-th road (1 \leq i \leq M) bidirectionally connects intersection U_i and intersection V_i, and it takes W_i minutes to traverse in either direction. There may be multiple roads connecting the same pair of intersections.

Today there are K delivery requests. The j-th request (1 \leq j \leq K) requires delivering a package to a customer at intersection D_j. All K delivery destination intersections are distinct, and none of them is the same as intersection S where the office is located. Takahashi must depart from intersection S where the office is located, visit all K delivery destinations, and then return to intersection S. He is free to choose the order in which he visits the delivery destinations. He may pass through the same intersection or the same road any number of times during his travel.

A delivery to a destination is automatically completed the moment Takahashi passes through that intersection, even if it is in the middle of traveling to another destination. In other words, if he passes through a delivery destination while heading to a different one, the delivery to that destination is also completed. The time for handing over packages is negligible.

Find the minimum total travel time (in minutes) to complete all deliveries and return to the office.

It is guaranteed that all delivery destinations are reachable from intersection S (since the roads are bidirectional, it is also possible to return from each delivery destination to intersection S).

Constraints

  • 2 \leq N \leq 10\,000
  • 1 \leq M \leq 20\,000
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • 1 \leq S \leq N
  • 1 \leq K \leq 15
  • 1 \leq D_j \leq N
  • All D_j are distinct
  • D_j \neq S
  • All delivery destinations are reachable from S
  • All input values are integers

Input

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
S K
D_1 D_2 \ldots D_K
  • The first line contains the number of intersections N and the number of roads M, separated by a space.
  • The following M lines each contain, for the i-th road (1 \leq i \leq M), the numbers of the two intersections U_i, V_i connected by the road and the travel time W_i (in minutes), separated by spaces.
  • The next line contains the intersection number S where the office is located and the number of deliveries K, separated by a space.
  • The next line contains the K delivery destination intersection numbers D_1, D_2, \ldots, D_K, separated by spaces.

Output

Output in a single line the minimum total travel time (in minutes) as an integer to visit all delivery destinations and return to the office.

Sample Input 1

4 5
1 2 2
2 3 3
3 4 4
1 4 7
1 3 10
1 2
3 4

Sample Output 1

16

Sample Input 2

6 8
1 2 3
1 3 5
2 3 1
2 4 7
3 5 4
4 5 2
4 6 3
5 6 6
1 3
4 5 6

Sample Output 2

26

Sample Input 3

10 14
1 2 5
1 3 12
2 3 4
2 4 8
3 5 3
4 5 6
4 6 2
5 7 7
6 7 4
6 8 9
7 9 3
8 9 5
8 10 2
9 10 6
1 5
3 5 7 9 10

Sample Output 3

54