実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : \(200\) 点
問題文
カトーくんは、とあるRPGのシナリオを作っています。 このRPGでは \(N\) 個の場面があり、各場面は既に「戦闘」か「空き地」のどちらかであると決まっています。 また、 \(M\) 個の場面間をつなぐ移動通路があり、\(i\) 番目の通路は、場面 \(a_i\) から 場面 \(b_i\) へ移動が可能です。 最初、RPGの主人公であるシンヤくんは、場面 \(1\) にいて、自由に通路を移動し、場面 \(N\) に到達したらゲームクリアです。
シンヤくんには「元気」と「疲労」の2種類の状態があります。 「元気」状態では戦闘に挑むことができますが、「疲労」状態では戦闘することができません。 「疲労」状態で「戦闘」場面に到達するとゲームオーバーとなります。
シンヤくんは「元気」状態でゲームを開始します。 「戦闘」場面を通過すると、疲れて「疲労」状態になります。 「疲労」状態から「元気」状態に戻るためには「回復所」を通過する必要があります。
「回復所」は任意の「空き地」場面に設置することができます。 場面 \(i \ (2 \leq i \leq N-1)\) に回復所を設置するコストは \(c_i\) です。
現在、「回復所」をどこに設置するかは決まっていません。 そこでカトーくんは、以下の条件を満たすように、「回復所」を設置することにしました。
- 場面 \(1\) から動き始めたシンヤくんが場面 \(N\)に向かうどのような移動を選んでも、任意の「戦闘」場面から他の「戦闘」場面に達する間に、少なくとも1回は「回復所」を通過する。
- ゲームクリア時のシンヤくんの状態は「疲労」でも「元気」でもよい。
以上の条件を満たすようにカトーくんが「回復所」を設置する際に必要なコストの合計の最小値を求めてください。
どのように「回復所」を設置しても条件を満たすことができなければ、 -1
を出力してください。
制約
- \(3 \leq N \leq 500\)
- \(N-1 \leq M \leq 1000\)
- \(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\)
- \(c_i = -1\) ならば、場面 \(i\) は「戦闘」場面である。
- \(c_i \geq 0\)ならば、場面 \(i\) は「空き地」場面であり、そこに「休憩所」を設置するコストは \(c_i\) である。
- \(1 \leq a_i , b_i \leq N \ (1 \leq i \leq M)\)
- 場面 \(a_i\) から、場面 \(b_i\) への移動通路があることを示す。
- \(N\) 頂点 \(M\) 辺の有向グラフとみたとき、全ての頂点に対し、頂点 \(1\) からのパスと、頂点 \(N\) へ向かうパスが存在する。また、閉路は存在しない。
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
\(N\) \(M\) \(c_2\) \(c_3\) \(\dots\) \(c_{N-1}\) \(a_1\) \(b_1\) \(a_2\) \(b_2\) \(\vdots\) \(a_M\) \(b_M\)
出力
条件を満たすような「回復所」の設置コストの合計の最小値を出力してください。
条件を満たすことができない場合は、 -1
を出力してください。
入力例 1
7 7 -1 100 10 1 -1 1 2 2 3 3 6 2 4 4 5 5 6 6 7
出力例 1
101
場面 \(3\) と場面 \(5\) を選ぶのが最適です。
入力例 2
4 3 -1 -1 1 2 2 3 3 4
出力例 2
-1
場面 \(2\) から場面 \(3\) の間に「休憩所」を設置することができません。