/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号が付いた N 頂点 M 辺の重み付き単純連結無向グラフが与えられます。辺 i (1 \leq i \leq M) は頂点 u_i と頂点 v_i を双方向に結び、重みは w_i です。
あるパスに対してその重みをそのパスに含まれる辺の重みの最大値とします。 また、f(x,y) を 頂点 x から頂点 y へのパスの重みとしてありえる最小値とします。
長さ K の数列 (A_1,A_2,\ldots,A_K) と (B_1,B_2,\ldots,B_K) が与えられます。ここで、A_i \neq B_j (1 \leq i,j \leq K) が成り立つことが保証されます。
数列 B を自由に並べ替えて、\displaystyle\sum_{i=1}^{K}f(A_i,B_i) を最小化してください。
制約
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)
- 1 \leq K \leq N
- 1 \leq u_i<v_i \leq N (1 \leq i \leq M)
- 1 \leq w_i \leq 10^9
- 1 \leq A_i,B_i \leq N (1 \leq i \leq K)
- A_i \neq B_j (1 \leq i,j \leq K)
- 与えられるグラフは単純かつ連結
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M A_1 A_2 \ldots A_K B_1 B_2 \ldots B_K
出力
\displaystyle\sum_{i=1}^{K}f(A_i,B_i) の最小値を出力せよ。
入力例 1
4 4 3 1 3 2 3 4 1 2 4 5 1 4 4 1 1 3 4 4 2
出力例 1
8
B を並び替えて、B=(2,4,4) としたとき、
- f(1,2)=5 : 頂点 1 から頂点 4 を経由し頂点 2 に行くパスがあり、辺 3 の重み 5 が最大値を取ります。また、辺の重みの最大値が 4 以下になるようなパスは存在しないため 5 が最小値です。
- f(1,4)=2 : 頂点 1 から頂点 3 を経由し頂点 4 に行くパスがあり、辺 1 の重み 2 が最大値を取ります。また、辺の重みの最大値が 1 以下になるようなパスは存在しないため 2 が最小値です。
- f(3,4)=1 : 頂点 3 から頂点 4 への辺を通るパスがあり、辺の重みは 1 でこれが辺の重みの最大値です。また、パスの重みが 0 以下になることはないため 1 が最小値です。
よって、この場合 \displaystyle \sum_{i=1}^{3}f(A_i,B_i)=5+2+1=8 となります。また、B をどのように並び替えても 7 以下になることはないため、答えは 8 です。
入力例 2
3 3 2 1 2 5 2 3 2 1 3 1 1 1 2 3
出力例 2
3
Score : 500 points
Problem Statement
You are given a simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N and edges are numbered 1 to M. Edge i (1 \leq i \leq M) connects vertices u_i and v_i bidirectionally and has weight w_i.
For a path, define its weight as the maximum weight of an edge in the path. Define f(x, y) as the minimum possible path weight of a path from vertex x to vertex y.
You are given two sequences of length K: (A_1, A_2, \ldots, A_K) and (B_1, B_2, \ldots, B_K). It is guaranteed that A_i \neq B_j (1 \leq i,j \leq K).
Permute the sequence B freely so that \displaystyle \sum_{i=1}^{K} f(A_i, B_i) is minimized.
Constraints
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)
- 1 \leq K \leq N
- 1 \leq u_i<v_i \leq N (1 \leq i \leq M)
- 1 \leq w_i \leq 10^9
- 1 \leq A_i,B_i \leq N (1 \leq i \leq K)
- The given graph is simple and connected.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M A_1 A_2 \ldots A_K B_1 B_2 \ldots B_K
Output
Print the minimum value of \displaystyle \sum_{i=1}^{K} f(A_i, B_i).
Sample Input 1
4 4 3 1 3 2 3 4 1 2 4 5 1 4 4 1 1 3 4 4 2
Sample Output 1
8
If we rearrange B as (2,4,4):
- f(1,2) = 5: The path from vertex 1 to vertex 2 passing through vertex 4 contains edge 3 with a maximum edge weight of 5. There is no path with a maximum edge weight less than or equal to 4, so 5 is the minimum possible.
- f(1,4) = 2: The path from vertex 1 to vertex 4 passing through vertex 3 contains edge 1 with a maximum edge weight of 2. There is no path with a maximum edge weight less than or equal to 1, so 2 is the minimum possible.
- f(3,4) = 1: The path from vertex 3 to vertex 4 passing through the direct edge contains an edge with a maximum edge weight of 1. No path can have a maximum weight 0 or less, so 1 is the minimum possible.
Thus, \displaystyle \sum_{i=1}^{3} f(A_i, B_i) = 5+2+1=8. No permutation of B yields 7 or less, so the answer is 8.
Sample Input 2
3 3 2 1 2 5 2 3 2 1 3 1 1 1 2 3
Sample Output 2
3