問題一覧 > 教育的問題

No.2916 累進コスト最小化

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : 👑 p-adic / テスター : 👑 binap
2 ProblemId : 10251 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-30 12:19:02

注意

この問題の実行時間制限は3500[ms]です。

問題文

入力の最初に 22 以上の整数 NN と 22 個の正整数 M,CM,C が与えられます。

　

ある国には NN 個の島と、それらを結ぶ MM 本の橋があります。この国の移動手段は橋を渡ることだけであり、22 個の島を結ぶ橋は高々 11 本しかありません。

島は NN 以下の各正整数 ii で番号づけられ島 ii と呼ばれ、橋は MM 以下の各正整数 mm で番号づけられ橋 mm と呼ばれています。

MM 以下の各正整数 mm に対し、

  • 橋 mm は島 imi_m と島 jmj_m（imi_m と jmj_m は 1≤im<jm≤N1 \leq i_m < j_m \leq N を満たす整数）を結んでいます。
  • 橋 mm を渡る際に、その時点での所持金が cc である人は通行料を ⌊crm⌋+wm\lfloor \frac{c}{r_m} \rfloor + w_m（rmr_m と wmw_m は cc に依存しない正整数）支払わなければならず、また所持金より多くの通行料を支払うことはできません。

　

CC 以下の各正整数 cc に対し、所持金が cc で島 11 にいる人が島 NN に移動することが可能であるか否かと、可能である場合は島 NN に移動後の所持金の最大値を求めてください。

入力

入力は以下の形式で標準入力から 1+M1 + M 行で与えられます：

  • 11 行目に N,M,CN, M, C が半角空白区切りで与えられます。
  • MM 以下の各正整数 mm に対し 2+m2 + m 行目に im,jm,rm,wmi_m,j_m,r_m,w_m が半角空白区切りで与えられます。
NN MM CC
i1i_1 j1j_1 r1r_1 w1w_1
⋮\vdots
iMi_M jMj_M rMr_M wMw_M

制約

入力は以下の制約を満たします：

  • NN は 2≤N≤102 \leq N \leq 10 を満たす整数である。
  • MM は 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2} を満たす整数である。
  • CC は 1≤C≤1051 \leq C \leq 10^5 を満たす整数である。
  • MM 以下の任意の正整数 mm に対し、
    • imi_m と jmj_m は 1≤im<jm≤N1 \leq i_m < j_m \leq N を満たす整数である。
    • rmr_m は 1≤rm≤C1 \leq r_m \leq C を満たす整数である。
    • wmw_m は 1≤wm≤C1 \leq w_m \leq C を満たす整数である。
  • MM 以下の任意の正整数 m0,m1m_0,m_1 に対し、m0≠m1m_0 \neq m_1 ならば (im0,jm0)≠(im1,jm1)(i_{m_0},j_{m_0}) \neq (i_{m_1},j_{m_1}) である。

出力

CC 以下の各正整数 cc に対し、所持金が cc で島 11 にいる人が島 NN に移動することが可能である場合は島 NN に移動後の所持金の最大値を、可能でない場合は-1を cc 行目に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2 1 1
1 2 1 1
出力
-1

最初の所持金を cc と置きます。1≤c≤C=11 \leq c \leq C = 1 より c=1c = 1 です。

島 11 から島 N=2N = 2 に移動するには、島 11 と島 22 を結ぶ橋 11 を渡る必要があります。橋 11 を渡るためには通行料を ⌊c1⌋+1=2\lfloor \frac{c}{1} \rfloor + 1 = 2 支払う必要があり、これは cc より大きいので支払えません。

サンプル2
入力
2 1 3
1 2 2 1
出力
0
0
1

最初の所持金を cc と置きます。1≤c≤C=31 \leq c \leq C = 3 です。

島 11 から島 N=2N = 2 に移動するには、島 11 と島 22 を結ぶ橋 11 を渡れば良いです。橋 11 を渡るためには通行料を ⌊c2⌋+1\lfloor \frac{c}{2} \rfloor + 1 支払う必要があります。

c=1c = 1 の時、⌊c2⌋+1=1\lfloor \frac{c}{2} \rfloor + 1 = 1 なので橋 11 を渡ることができ、島 22 に移動した時点での所持金が c−1=0c - 1 = 0 になります。これより多い所持金を持って島 22 に移動することはできません。

c=2c = 2 の時、⌊c2⌋+1=2\lfloor \frac{c}{2} \rfloor + 1 = 2 なので橋 11 を渡ることができ、島 22 に移動した時点での所持金が c−2=0c - 2 = 0 になります。これより多い所持金を持って島 22 に移動することはできません。

c=3c = 3 の時、⌊c2⌋+1=2\lfloor \frac{c}{2} \rfloor + 1 = 2 なので橋 11 を渡ることができ、島 22 に移動した時点での所持金が c−2=1c - 2 = 1 になります。これより多い所持金を持って島 22 に移動することはできません。

サンプル3
入力
4 4 5
1 2 3 2
1 3 2 1
2 4 3 1
3 4 2 1
出力
-1
-1
0
0
1

最初の所持金を cc と置きます。1≤c≤C=61 \leq c \leq C = 6 です。

島 11 から島 N=4N = 4 に移動するには、島 11 と島 22 を結ぶ橋 11 を渡ってから島 22 と島 44 を結ぶ橋 33 を渡るか、島 11 と島 33 を結ぶ橋 22 を渡ってから島 33 と島 44 を結ぶ橋 44 を渡れば良いです。前者の経路では橋 11 を渡るために通行料を ⌊c3⌋+2\lfloor \frac{c}{3} \rfloor + 2 支払う必要があり、残額を c′c' と置くと橋 33 を渡るために通行料を更に ⌊c′3⌋+1\lfloor \frac{c'}{3} \rfloor + 1 支払う必要があります。後者の経路では橋 22 を渡るために通行料を ⌊c3⌋+1\lfloor \frac{c}{3} \rfloor + 1 支払う必要があり、残額を c′c' と置くと橋 44 を渡るために通行料を更に ⌊c′2⌋+1\lfloor \frac{c'}{2} \rfloor + 1 支払う必要があります。

c=1c = 1 の時、前者の経路では ⌊c3⌋+2=2>c\lfloor \frac{c}{3} \rfloor + 2 = 2 > c なので橋 11 を渡れません。後者の経路では ⌊c2⌋+1=1=c\lfloor \frac{c}{2} \rfloor + 1 = 1 = c なので橋 22 を渡ることができますが、島 33 に移動した時点での所持金が c′=c−1=0c' = c - 1 = 0 になり、⌊c′2⌋+1=1>c′\lfloor \frac{c'}{2} \rfloor + 1 = 1 > c' なので橋 44 を渡れません。いずれの経路でも島 44 に移動できません。

c=2c = 2 の時、前者の経路では ⌊c3⌋+2=2=c\lfloor \frac{c}{3} \rfloor + 2 = 2 = c なので橋 11 を渡ることができますが、島 22 に移動した時点での所持金が c′=c−2=0c' = c - 2 = 0 になり、⌊c′3⌋+1=1>c′\lfloor \frac{c'}{3} \rfloor + 1 = 1 > c' なので橋 33 を渡れません。後者の経路では ⌊c2⌋+1=2=c\lfloor \frac{c}{2} \rfloor + 1 = 2 = c なので橋 22 を渡ることができますが、島 33 に移動した時点での所持金が c′=c−2=0c' = c - 2 = 0 になり、⌊c′2⌋+1=1>c′\lfloor \frac{c'}{2} \rfloor + 1 = 1 > c' なので橋 44 を渡れません。いずれの経路でも島 44 に移動できません。

c=3c = 3 の時、前者の経路では ⌊c3⌋+2=3\lfloor \frac{c}{3} \rfloor + 2 = 3 なので橋 11 を渡ることができ、島 22 に移動した時点での所持金が c′=c−3=0c' = c - 3 = 0 になり、⌊c′3⌋+1=1>c′\lfloor \frac{c'}{3} \rfloor + 1 = 1 > c' なので橋 33 を渡ることができません。後者の経路では ⌊c2⌋+1=2<c\lfloor \frac{c}{2} \rfloor + 1 = 2 < c なので橋 22 を渡ることができ、島 33 に移動した時点での所持金が c′=c−2=1c' = c - 2 = 1 になり、⌊c′2⌋+1=1=c′\lfloor \frac{c'}{2} \rfloor + 1 = 1 = c' なので橋 44 を渡ることができ、島 44 に移動した時点での所持金が c′−1=0c' - 1 = 0 になります。これより多い所持金を持って島 44 に移動することはできません。

c=4c = 4 の時、前者の経路では ⌊c3⌋+2=3<c\lfloor \frac{c}{3} \rfloor + 2 = 3 < c なので橋 11 を渡ることができ、島 22 に移動した時点での所持金が c′=c−3=1c' = c - 3 = 1 になり、⌊c′3⌋+1=1=c′\lfloor \frac{c'}{3} \rfloor + 1 = 1 = c' なので橋 33 を渡ることができ、島 44 に移動した時点での所持金が c′−1=0c' - 1 = 0 になります。後者の経路では ⌊c2⌋+1=3<c\lfloor \frac{c}{2} \rfloor + 1 = 3 < c なので橋 22 を渡ることができ、島 33 に移動した時点での所持金が c′=c−3=1c' = c - 3 = 1 になり、⌊c′2⌋+1=1=c′\lfloor \frac{c'}{2} \rfloor + 1 = 1 = c' なので橋 33 を渡ることができ、島 44 に移動した時点での所持金が c′−1=0c' - 1 = 0 になります。従って前者の経路と後者の経路で残る金額は同じです。これより多い所持金を持って島 44 に移動することはできません。

c=5c = 5 の時、前者の経路では ⌊c3⌋+1=3<c\lfloor \frac{c}{3} \rfloor + 1 = 3 < c なので橋 11 を渡ることができ、島 22 に移動した時点での所持金が c′=c−3=2c' = c - 3 = 2 になり、⌊c′3⌋+1=1<c′\lfloor \frac{c'}{3} \rfloor + 1 = 1 < c' なので橋 33 を渡ることができ、島 44 に移動した時点での所持金が c′−1=1c' - 1 = 1 になります。後者の経路では ⌊c2⌋+1=3<c\lfloor \frac{c}{2} \rfloor + 1 = 3 < c なので橋 22 を渡ることができ、島 33 に移動した時点での所持金が c′=c−3=2c' = c - 3 = 2 になり、⌊c′2⌋+1=2=c′\lfloor \frac{c'}{2} \rfloor + 1 = 2 = c' なので橋 33 を渡ることができ、島 44 に移動した時点での所持金が c′−2=0c' - 2 = 0 になります。従って前者の経路の方が多く所持金を残せます。これより多い所持金を持って島 44 に移動することはできません。

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