問題一覧 > 通常問題

No.1814 Uribo Road (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : MasKoaTSMasKoaTS / テスター : ShirotsumeShirotsume
0 ProblemId : 7106 / 自分の提出
問題文最終更新日: 2024-12-01 12:42:04

注意点

本問は問題 Uribo Road問題文は同じですが、制約・実行時間制限が異なります

なお、本問は実行時間制限が少し厳しめなので、一部の言語・処理系では想定解でも TLE になる可能性があります。
特に本問を Python を用いて解答する場合、処理系に PyPy3 を選ぶことを推奨します。

問題文

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

ii (1iM)(1 \leq i \leq M) は地点 AiA_{i} と地点 BiB_{i} を結んでおり、その間の距離は CiC_{i} です。

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

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

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

制約

問題 Uribo Road と異なる部分を 赤字 で表示しています。

  • 2N2002 \leq N \leq \boldsymbol{ \textcolor {red} {200} }

  • N1MN×(N1)2\displaystyle N-1 \leq M \leq \boldsymbol{ \textcolor {red} {\frac{N \times (N-1) }{2} } }

  • 1Kmin(5,M)1 \leq K \leq \min ( \boldsymbol{ \textcolor {red} {5} }, M)

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

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

  • 1Ai,BiN1 \leq A_{i},B_{i} \leq N   かつ   AiBiA_{i} \neq B_{i} (1iM)(1 \leq i \leq M)

  • (Ai,Bi)(Aj,Bj)(A_{i},B_{i}) \neq (A_{j},B_{j})   かつ   (Ai,Bi)(Bj,Aj)(A_{i},B_{i}) \neq (B_{j},A_{j}) (1i<jM)(1 \leq i < j \leq M)

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

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

  • 入力はすべて整数

入力

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

NN MM KK
R1R_{1} R2R_{2} \cdots RKR_{K}
A1A_{1} B1B_{1} C1C_{1}
A2A_{2} B2B_{2} C2C_{2}
     \vdots
AMA_{M} BMB_{M} CMC_{M}
  • 11 行目には NNMMKK がこの順に半角スペース区切りで与えられる

  • 22 行目には R1,R2,,RKR_{1},R_{2},\cdots,R_{K} がこの順に半角スペース区切りで与えられる

  • (2+i)(2+i) (1iM)(1 \leq i \leq M) 行目には AiA_{i}BiB_{i}CiC_{i} がこの順に半角スペース区切りで与えられる

出力

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

サンプル

サンプル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

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

サンプル2
入力
6 5 5
2 4 3 5 1
1 2 2
3 2 4
2 4 6
5 4 8
4 6 10
出力
42

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

同じ道を 22 回以上通っても構いません。

サンプル3
入力
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

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

最終地点を 22 回以上訪問しても構いません。

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