問題一覧 > 通常問題

No.1812 Uribo Road

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 : MasKoaTSMasKoaTS / テスター : ShirotsumeShirotsume 👑 ygussanyygussany
4 ProblemId : 7295 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 20:49:33

追記(2022/04/25)

yukicoderの数式表示がMathJaxからKaTeXへ移行したことに伴い、問題文・解説の更新を行いました。

何か不備等ありましたら、作問者の方までご一報いただけると幸いです。

注意

本問の実行時間制限はテストケース $1$ つあたり $\boldsymbol{ \textcolor {red} {5.0} }$ です。

問題文

ハッコウ山には $1, 2, \dots, N$ の番号が付いた $N$ 個の地点があり、これらの地点は
$1, 2, \dots, M$ の番号が付いた $M$ 本の双方向に移動できる道で結ばれています。

道 $i$ $(1 \leq i \leq M)$ は地点 $A_{i}$ と地点 $B_{i}$ を結んでおり、その間の距離は $C_{i}$ です。

コアさんは、この山の地点 $1$ にある自宅から地点 $N$ にあるコウメ学園に通っており、その際、
$K$ 本の道 $R_{1},R_{2},\dots,R_{K}$ に生息するイノシシをすべて撫で撫でするのが日課です。

コアさんの自宅からコウメ学園までの移動経路を、道 $R_{1},R_{2},\dots,R_{K}$ をすべて $1$ 回以上通過し、
かつその際の移動距離が最小になるように決定するとき、移動距離を求めてください。

ただし、同じ道を $2$ 回以上通過したり、地点 $N$ を $2$ 回以上訪問したりしても構いません。

制約

  • $ 2 \leq N \leq 10^{4} $

  • $\displaystyle N-1 \leq M \leq \min \left( 2 \times 10^{4}, \frac{N \times (N-1) }{2} \right)$

  • $1 \leq K \leq \min (12,M)$

  • $1 \leq R_{i} \leq M$ $(1 \leq i \leq K)$

  • $R_{i} \neq R_{j}$ $(1 \leq i < j \leq K)$

  • $1 \leq A_{i},B_{i} \leq N$   かつ   $A_{i} \neq B_{i}$ $(1 \leq i \leq M)$

  • $(A_{i},B_{i}) \neq (A_{j},B_{j})$   かつ   $(A_{i},B_{i}) \neq (B_{j},A_{j})$ $(1 \leq i < j \leq M)$

  • $1 \leq C_{i} \leq 10^{4}$ $(1 \leq i \leq M)$

  • 任意の $2$ 地点間は $1$ 本以上の道を通って移動できる

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$ $K$
$R_{1}$ $R_{2}$ $\cdots$ $R_{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$ 行目には $R_{1},R_{2},\dots,R_{K}$ がこの順に空白区切りで与えられる

  • $(2+i)$ $(1 \leq i \leq M)$ 行目には $A_{i}$ と $B_{i}$ と $C_{i}$ がこの順に空白区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
5 6 2
3 4
1 2 3
1 3 1
2 3 10
3 4 20
3 5 5
4 5 7
出力
40

地点 $1 \to 2 \to 3 \to 4 \to 5$ の順に移動すれば、地点 $2$ と地点 $3$ を結ぶ道 $3$ 、及び地点 $3$ と地点 $4$ を
結ぶ道 $4$ の両方を通過でき、その際の地点 $5$ までの移動距離が最小になります。

サンプル2
入力
4 6 3
2 3 4
1 2 4
1 3 6
1 4 1
2 3 3
2 4 2
3 4 1
出力
13

地点 $1 \to 3 \to 2 \to 4 \to 1 \to 4$ の順に移動すれば良いです。

同じ道を $2$ 回以上通過したり、最終地点を $2$ 回以上訪問したりしても構いません。

サンプル3
入力
6 6 6
2 4 6 1 3 5
1 2 1
3 1 2
4 2 3
2 5 4
3 4 5
6 5 6
出力
22

地点 $1 \to 3 \to 4 \to 2 \to 1 \to 2 \to 5 \to 6$ の順に移動すれば良いです。

サンプル4
入力
10 20 12
13 10 6 19 14 12 16 4 3 17 2 9
5 8 43
4 7 3
6 7 1853
2 7 1
6 5 1
4 3 7153
10 4 108
9 5 32
10 1 8
3 2 45
6 1 5281
6 9 7331
1 8 19
10 5 78
6 4 4
9 1 147
1 3 2
7 9 21
10 9 36
3 9 8887
出力
16742

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。