레이팅 미적용IOI 町にはN 個の交差点があり,1 からN までの番号が付いている.また,M 本の道があり,1 からM
までの番号が付いている.それぞれの道は2 個の異なる交差点を双方向に結んでいる.道i (1 ≦i ≦M) は
交差点Ai と交差点Bi を結んでいる.2 本の異なる道が同じ交差点の組を結ぶことはない.これらの道には
1 以上M 以下の整数で表される色が塗られており,道i の現在の色はCi である.複数の道が同じ色で塗ら
れているかもしれない.
JOI 社はIOI 町の交差点を移動するロボットを開発した.あなたがこのロボットに道の色を指示すると,
ロボットは指示された色の道を通り隣接した交差点に移動する.ただし,ロボットが現在いる交差点につな
がれた道のうちに,指示された色の道が2 本以上存在すると,次に進むべき道を判別できずに停止してし
まう.
あなたの目的は,現在交差点1 にいるロボットに何回かの指示を出して,交差点N に移動させることで
ある.ただし,現在の道の色ではそれができるとは限らないため,何本かの道の色を事前に塗り替えること
で,ロボットを交差点N に移動させることができるようにしたい.道i (1 ≦i ≦M) はPi 円をかけて,1 以
上M 以下の好きな整数の色に塗り替えることが出来る.
交差点と道の情報が与えられたとき,必要な金額の最小値を求めるプログラムを作成せよ.ただし,どの
ように道の色を塗り替えてもロボットを交差点N に移動させることができない場合は,代わりに-1 を出力
せよ.
• 2 ≦N ≦100 000.
• 1 ≦M ≦200 000.
• 1 ≦Ai < Bi ≦N (1 ≦i ≦M).
• (Ai, Bi) , (Aj, Bj) (1 ≦i < j ≦M).
• 1 ≦Ci ≦M (1 ≦i ≦M).
• 1 ≦Pi ≦1 000 000 000 (1 ≦i ≦M).
- (34 点) N ≦1 000,M ≦2 000.
- (24 点) Pi = 1 (1 ≦i ≦M).
- (42 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
A1 B1 C1 P1
...
AM BM CM PM
標準出力に必要な金額の最小値を1 行で出力せよ.ただし,どのように道の色を塗り替えてもロボットを
交差点N に移動させることができない場合は,代わりに-1 を出力せよ.
第20 回日本情報オリンピック(JOI 2020/2021) 本選
2021 年2 月14 日(オンライン開催)
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
3
5 2
1 4 1 2
3 5 1 4
-1
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
1
13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
7