No.1 道のショートカット

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 325
作問者 : yuki2006yuki2006
13 ProblemId : 17 / 出題時の順位表
問題文最終更新日: 2019-04-17 16:55:02

問題文

\(N\)個の町があります。それぞれ\(1 \ldots N\)と番号がふられています。
それぞれの街は直接、道でつながっているものもあれば、つながってないものがあります。
それぞれの道は 町\(S_i\)から町\(T_i\)に行くのに \(Y_i\)のコスト(お金:円)がかかり、\(M_i\) 単位時間 かかります。

あなたは \(1\) の町にいます。
\(N\) の都市に行きたいと思っています。
何個道や町を経由してもいいですが、あなたは今\(C\)円しか持っていません。

(つまり、通った道のコスト \(Yi\) の合計が\(C\)以下にしないといけない。)

その中で一番早く着く道を選べた時、合計の単位時間を答えてください。
この制約の中で辿りつけない場合 \(-1\)を返してください。

入力

\(N\)
\(C\)
\(V\)
\(S_1\ S_2\ S_3\ \dots\ S_V\)
\(T_1\ T_2\ T_3\ \dots\ T_V\)
\(Y_1\ Y_2\ Y_3\ \dots\ Y_V\)
\(M_1\ M_2\ M_3\ \dots\ M_V\)

\(1\)行目に、町の数を表す整数 \( N\ ( 2 \leq N \leq 50 ) \) が与えられる。
\(2\)行目に、手持ちのお金を表す整数 \( C\ ( 1 \leq C \leq 300 ) \) が与えられる。
\(3\)行目に、道の数を表す整数 \( V\ ( 1 \leq V \leq 1500 ) \) が与えられる。
\(4\)行目に、\(S_i\ ( 1 \leq S_i \leq N ) \)が\(V\)個スペース区切りで与えられる。
\(5\)行目に、\(T_i\ ( S_i \lt T_i \leq N ) \)が\(V\)個スペース区切りで与えられる。
\(6\)行目に、\(Y_i\ ( 1 \leq Y_i \leq C ) \)が\(V\)個スペース区切りで与えられる。
\(7\)行目に、\(M_i\ ( 1 \leq M_i \leq 1000 ) \)が\(V\)個スペース区切りで与えられる。

\(S_i, T_i, Y_i, M_i\) は それぞれ \(i\) インデックス で町 \(S_i\) \(\rightarrow\) 町\(T_i\) (有向グラフ)の移動に コスト\(Y_i\) がかかり、\(M_i\) 単位時間かかるという意味です。

制約的につまり、町どうしを道でつないだ後にできるグラフは閉路(ループ)がないとし、番号的には \(S_i \lt T_i\)となっているとする。
つまり、番号的に戻る経路(例えば町\(3\)から町\(1\)など)へは考えなくてもよい。
道の接続的に町\(N\)に辿りつけない場合もあります。
\(S_i \rightarrow T_i\)への経路が複数ある場合があります。

出力

\(1\)の町から\(N\)の町へ行く一番早く着く道を選べた時、合計の単位時間を答えてください。
この制約の中で辿りつけない場合 -1を返してください。
最後に改行してください。

サンプル

サンプル1
入力
3
100
3
1 2 1
2 3 3
10 90 10
10 10 50
出力
20

\(1 \rightarrow 3\) と行くと コスト\(10\)だが、単位時間が\(50\)掛かる。
\(1 \rightarrow 2 \rightarrow 3\) と行くと 一文無しになるが、 \(20\)単位時間と早いのでこちらを選択する。

サンプル2
入力
3
100
3
1 2 1
2 3 3
1 100 10
10 10 50
出力
50

\(1 \rightarrow 2 \rightarrow 3\) と行くと 時間は\(20\)と短いが、コスト\(101\)かかるため選択できない。

サンプル3
入力
10
10
19
1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9
3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10
8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6
8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4
出力
-1

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。