Skip to content
Sign in

ロボット (Robot)

Unrated
日本語

Language

Contribute a translation
Time limit
4000 ms
Memory limit
512 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

IOI 町には \(N\) 個の交差点があり，\(1\) から \(N\) までの番号が付いている．また，\(M\) 本の道があり，\(1\) から \(M\) までの番号が付いている．それぞれの道は \(2\) 個の異なる交差点を双方向に結んでいる．道 \(i\) (\(1 \leqq i \leqq M\)) は交差点 \(A_i\) と交差点 \(B_i\) を結んでいる．\(2\) 本の異なる道が同じ交差点の組を結ぶことはない．これらの道には \(1\) 以上 \(M\) 以下の整数で表される色が塗られており，道 \(i\) の現在の色は \(C_i\) である．複数の道が同じ色で塗られているかもしれない．

JOI 社は IOI 町の交差点を移動するロボットを開発した．あなたがこのロボットに道の色を指示すると，ロボットは指示された色の道を通り隣接した交差点に移動する．ただし，ロボットが現在いる交差点につながれた道のうちに，指示された色の道が \(2\) 本以上存在すると，次に進むべき道を判別できずに停止してしまう．

あなたの目的は，現在交差点 \(1\) にいるロボットに何回かの指示を出して，交差点 \(N\) に移動させることである．ただし，現在の道の色ではそれができるとは限らないため，何本かの道の色を事前に塗り替えることで， ロボットを交差点 \(N\) に移動させることができるようにしたい．道 \(i\) (\(1 \leqq i \leqq M\)) は \(P_i\) 円をかけて，\(1\) 以上 \(M\) 以下の好きな整数の色に塗り替えることが出来る．

交差点と道の情報が与えられたとき，必要な金額の最小値を求めるプログラムを作成せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 \(N\) に移動させることができない場合は，代わりに -1 を出力せよ．

Input

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

\(N\) \(M\)
\(A_1\) \(B_1\) \(C_1\) \(P_1\)
\(\vdots\)
\(A_M\) \(B_M\) \(C_M\) \(P_M\)

Output

標準出力に必要な金額の最小値を \(1\) 行で出力せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 \(N\) に移動させることができない場合は，代わりに -1 を出力せよ．

Constraints

  • \(2 \leqq N \leqq 100\,000\)．
  • \(1 \leqq M \leqq 200\,000\)．
  • \(1 \leqq A_i < B_i \leqq N\) (\(1 \leqq i \leqq M\))．
  • \((A_i, B_i) \neq (A_j, B_j)\) (\(1 \leqq i < j \leqq M\))．
  • \(1 \leqq C_i \leqq M\) (\(1 \leqq i \leqq M\))．
  • \(1 \leqq P_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq M\))．

Subtasks

  1. (\(34\) 点) \(N \leqq 1\,000\)，\(M \leqq 2\,000\)．
  2. (\(24\) 点) \(P_i = 1\) (\(1 \leqq i \leqq M\))．
  3. (\(42\) 点) 追加の制約はない．

Examples

Sample input 1
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
Sample output 1
3

\(1\) 円で道 \(4\) を色 \(3\) から色 \(4\) に塗り替え，\(2\) 円で道 \(6\) を色 \(4\) から色 \(2\) に塗り替える．合計 \(3\) 円かかる．

この結果，交差点 \(1\) にいるロボットに色 \(2\) を指示することで，ロボットを交差点 \(2\) に移動させることができる．続けて，ロボットに色 \(4\) を指示することで，ロボットを交差点 \(4\) に移動させることができる．

\(2\) 円以下でロボットを交差点 \(4\) に移動させることは不可能であるため，\(3\) を出力する．

Sample input 2
5 2
1 4 1 2
3 5 1 4
Sample output 2
-1

道をどのように塗り替えても，ロボットを交差点 \(5\) に移動させることはできない．したがって，\(-1\) を出力する．

Sample input 3
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
Sample output 3
1

この入力例は小課題 \(2\) の制約を満たす．

Sample input 4
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
Sample output 4
7

Notes

JOI 2021 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source