問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 502
作問者 : yuki2006yuki2006
18 ProblemId : 17 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-20 03:41:06

問題文

\(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

サンプル4
入力
2
1
2
1 1
2 2
1 2
100 10
出力
100

多重辺があることにも気をつけてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。