No.1814 Uribo Road (Easy)
タグ : / 解いたユーザー数 34
作問者 : MasKoaTS / テスター : Shirotsume
追記(2022/04/25)
yukicoderの数式表示がMathJaxからKaTeXへ移行したことに伴い、問題文・解説の更新を行いました。
何か不備等ありましたら、作問者の方までご一報いただけると幸いです。
注意点
本問は問題 Uribo Road と問題文は同じですが、制約・実行時間制限が異なります。
なお、本問は実行時間制限が少し厳しめなので、一部の言語・処理系では想定解でも TLE になる可能性があります。
特に本問を Python を用いて解答する場合、処理系に PyPy3 を選ぶことを推奨します。
問題文
ハッコウ山には $1, 2, \cdots, N$ の番号が付いた $N$ 個の地点があり、これらの地点は
$1, 2, \cdots, M$ の番号が付いた $M$ 本の双方向に移動できる道で結ばれています。
道 $i$ $(1 \leq i \leq M)$ は地点 $A_{i}$ と地点 $B_{i}$ を結んでおり、その間の距離は $C_{i}$ です。
コアさんは、この山の地点 $1$ にある自宅から地点 $N$ にあるコウメ学園に通っており、その際、
$K$ 本の道 $R_{1},R_{2},\cdots,R_{K}$ に生息するイノシシをすべて撫で撫でするのが日課です。
コアさんの自宅からコウメ学園までの移動経路を、道 $R_{1},R_{2},\cdots,R_{K}$ をすべて $1$ 回以上通過し、
かつその際の移動距離が最小になるように決定するとき、移動距離を求めてください。
ただし、同じ道を $2$ 回以上通過したり、地点 $N$ を $2$ 回以上訪問したりしても構いません。
制約
問題 Uribo Road と異なる部分を 赤字 で表示しています。
$2 \leq N \leq \boldsymbol{ \textcolor {red} {200} }$
$\displaystyle N-1 \leq M \leq \boldsymbol{ \textcolor {red} {\frac{N \times (N-1) }{2} } }$
$1 \leq K \leq \min ( \boldsymbol{ \textcolor {red} {5} }, 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},\cdots,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
入力
6 5 5 2 4 3 5 1 1 2 2 3 2 4 2 4 6 5 4 8 4 6 10
出力
42
地点 $1 \to 2 \to 3 \to 2 \to 4 \to 5 \to 4 \to 6$ の順に移動すれば良いです。
同じ道を $2$ 回以上通っても構いません。
サンプル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
地点 $1 \to 3 \to 2 \to 4 \to 1 \to 4$ の順に移動すれば良いです。
最終地点を $2$ 回以上訪問しても構いません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。