[ABC073D] joisino's travel
题意翻译
一个人旅行,必须经过指定的r个城市,问最短的路程是多少。他可以从任意一个城市开始,任意一个城市结束。保证图是连通的。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc073/tasks/abc073_d
Atcoder国には $ N $ 個の町があり、$ M $ 本の双方向に移動可能な道で結ばれています。
また、 $ i $ 本目の道は町 $ A_i $ と町 $ B_i $ の間を距離 $ C_i $ で結んでいます。
joisinoお姉ちゃんは、この国の $ R $ 個の町 $ r_1,r_2..r_R $ を訪れることとなりました。
最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。
町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を答えてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ R $ $ r_1 $ $ ... $ $ r_R $ $ A_1 $ $ B_1 $ $ C_1 $ $ : $ $ A_M $ $ B_M $ $ C_M $
输出格式
町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を出力せよ。
输入输出样例
输入样例 #1
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4
输出样例 #1
2
输入样例 #2
3 3 2
1 3
2 3 2
1 3 6
1 2 2
输出样例 #2
4
输入样例 #3
4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6
输出样例 #3
3
说明
### 制約
- $ 2≦N≦200 $
- $ 1≦M≦N×(N-1)/2 $
- $ 2≦R≦min(8,N) $ ( $ min(8,N) $ は $ 8 $ と $ N $ のうち小さい方)
- $ r_i≠r_j\ (i≠j) $
- $ 1≦A_i,B_i≦N\ ,\ A_i≠B_i $
- $ (A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j)\ (i≠j) $
- $ 1≦C_i≦100000 $
- すべての町の間は道のみで移動することができる。
- 入力は全て整数である。
### Sample Explanation 1
例えば、町 $ 1 $ ,町 $ 2 $ ,町 $ 3 $ の順番で訪れると、移動距離が $ 2 $ となり、最小となります。
### Sample Explanation 2
町 $ 1 $ を訪れたあとに町 $ 3 $ を訪れても、町 $ 3 $ を訪れたあとに町 $ 1 $ を訪れても、町 $ 1 $ と町 $ 3 $ の間の最短距離は $ 4 $ であるため、どの順番を選んだとしても答えは $ 4 $ となります。