問題一覧 >
通常問題
No.1814 Uribo Road (Easy)
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 34
作問者 :
MasKoaTS
/ テスター :
Shirotsume
問題文最終更新日: 2024-12-01 12:42:04
注意点
本問は問題 Uribo Road
と問題文は同じですが、制約・実行時間制限が異なります。
なお、本問は実行時間制限が少し厳しめなので、一部の言語・処理系では想定解でも TLE になる可能性があります。
特に本問を Python を用いて解答する場合、処理系に PyPy3 を選ぶことを推奨します。
問題文
ハッコウ山には 1,2,⋯,N の番号が付いた N 個の地点があり、
これらの地点は 1,2,⋯,M の番号が付いた M 本の双方向に移動できる道で結ばれています。
道 i (1≤i≤M) は地点 Ai と地点 Bi を結んでおり、その間の距離は Ci です。
コアさんは、この山の地点 1 にある自宅から地点 N にあるコウメ学園に通っており、
その際、K 本の道 R1,R2,⋯,RK に生息するイノシシをすべて撫で撫でするのが日課です。
コアさんの自宅からコウメ学園までの移動経路を、道 R1,R2,⋯,RK をすべて 1 回以上通過し、
かつ移動経路全体の距離が最小になるように決定するとき、その移動距離を求めてください。
ただし、同じ道を 2 回以上通過したり、地点 N を 2 回以上訪問したりしても構いません。
制約
問題 Uribo Road と異なる部分を
赤字 で表示しています。
2≤N≤200
N−1≤M≤2N×(N−1)
1≤K≤min(5,M)
1≤Ri≤M (1≤i≤K)
Ri=Rj (1≤i<j≤K)
1≤Ai,Bi≤N かつ Ai=Bi (1≤i≤M)
(Ai,Bi)=(Aj,Bj) かつ
(Ai,Bi)=(Bj,Aj) (1≤i<j≤M)
1≤Ci≤104 (1≤i≤M)
任意の 2 地点間は 1 本以上の道を通って移動できる
入力はすべて整数
入力
入力は次の形式で与えられます。
N M K
R1 R2 ⋯ RK
A1 B1 C1
A2 B2 C2
⋮
AM BM CM
1 行目には N と M と K がこの順に半角スペース区切りで与えられる
2 行目には R1,R2,⋯,RK がこの順に半角スペース区切りで与えられる
(2+i) (1≤i≤M) 行目には Ai と Bi と Ci がこの順に半角スペース区切りで与えられる
出力
答えを 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→2→3→4→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→2→3→2→4→5→4→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→3→2→4→1→4 の順に移動すれば良いです。
最終地点を 2 回以上訪問しても構いません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。