No.2916 累進コスト最小化
タグ : / 解いたユーザー数 23
作問者 : 👑
p-adic
/ テスター :
👑 
binap
注意
この問題の実行時間制限は3500[ms]です。
問題文
入力の最初に $2$ 以上の整数 $N$ と $2$ 個の正整数 $M,C$ が与えられます。
ある国には $N$ 個の島と、それらを結ぶ $M$ 本の橋があります。この国の移動手段は橋を渡ることだけであり、$2$ 個の島を結ぶ橋は高々 $1$ 本しかありません。
島は $N$ 以下の各正整数 $i$ で番号づけられ島 $i$ と呼ばれ、橋は $M$ 以下の各正整数 $m$ で番号づけられ橋 $m$ と呼ばれています。
$M$ 以下の各正整数 $m$ に対し、
- 橋 $m$ は島 $i_m$ と島 $j_m$（$i_m$ と $j_m$ は $1 \leq i_m < j_m \leq N$ を満たす整数）を結んでいます。
- 橋 $m$ を渡る際に、その時点での所持金が $c$ である人は通行料を $\lfloor \frac{c}{r_m} \rfloor + w_m$（$r_m$ と $w_m$ は $c$ に依存しない正整数）支払わなければならず、また所持金より多くの通行料を支払うことはできません。
$C$ 以下の各正整数 $c$ に対し、所持金が $c$ で島 $1$ にいる人が島 $N$ に移動することが可能であるか否かと、可能である場合は島 $N$ に移動後の所持金の最大値を求めてください。
入力
入力は以下の形式で標準入力から $1 + M$ 行で与えられます：
- $1$ 行目に $N, M, C$ が半角空白区切りで与えられます。
- $M$ 以下の各正整数 $m$ に対し $2 + m$ 行目に $i_m,j_m,r_m,w_m$ が半角空白区切りで与えられます。
$N$ $M$ $C$ $i_1$ $j_1$ $r_1$ $w_1$ $\vdots$ $i_M$ $j_M$ $r_M$ $w_M$
制約
入力は以下の制約を満たします：
- $N$ は $2 \leq N \leq 10$ を満たす整数である。
- $M$ は $1 \leq M \leq \frac{N(N-1)}{2}$ を満たす整数である。
- $C$ は $1 \leq C \leq 10^5$ を満たす整数である。
- $M$ 以下の任意の正整数 $m$ に対し、
- $i_m$ と $j_m$ は $1 \leq i_m < j_m \leq N$ を満たす整数である。
- $r_m$ は $1 \leq r_m \leq C$ を満たす整数である。
- $w_m$ は $1 \leq w_m \leq C$ を満たす整数である。
- $M$ 以下の任意の正整数 $m_0,m_1$ に対し、$m_0 \neq m_1$ ならば $(i_{m_0},j_{m_0}) \neq (i_{m_1},j_{m_1})$ である。
出力
$C$ 以下の各正整数 $c$ に対し、所持金が $c$ で島 $1$ にいる人が島 $N$ に移動することが可能である場合は島 $N$ に移動後の所持金の最大値を、可能でない場合は-1を $c$ 行目に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 1 1 1 2 1 1
出力
-1
最初の所持金を $c$ と置きます。$1 \leq c \leq C = 1$ より $c = 1$ です。
島 $1$ から島 $N = 2$ に移動するには、島 $1$ と島 $2$ を結ぶ橋 $1$ を渡る必要があります。橋 $1$ を渡るためには通行料を $\lfloor \frac{c}{1} \rfloor + 1 = 2$ 支払う必要があり、これは $c$ より大きいので支払えません。
サンプル2
入力
2 1 3 1 2 2 1
出力
0 0 1
最初の所持金を $c$ と置きます。$1 \leq c \leq C = 3$ です。
島 $1$ から島 $N = 2$ に移動するには、島 $1$ と島 $2$ を結ぶ橋 $1$ を渡れば良いです。橋 $1$ を渡るためには通行料を $\lfloor \frac{c}{2} \rfloor + 1$ 支払う必要があります。
$c = 1$ の時、$\lfloor \frac{c}{2} \rfloor + 1 = 1$ なので橋 $1$ を渡ることができ、島 $2$ に移動した時点での所持金が $c - 1 = 0$ になります。これより多い所持金を持って島 $2$ に移動することはできません。
$c = 2$ の時、$\lfloor \frac{c}{2} \rfloor + 1 = 2$ なので橋 $1$ を渡ることができ、島 $2$ に移動した時点での所持金が $c - 2 = 0$ になります。これより多い所持金を持って島 $2$ に移動することはできません。
$c = 3$ の時、$\lfloor \frac{c}{2} \rfloor + 1 = 2$ なので橋 $1$ を渡ることができ、島 $2$ に移動した時点での所持金が $c - 2 = 1$ になります。これより多い所持金を持って島 $2$ に移動することはできません。
サンプル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
最初の所持金を $c$ と置きます。$1 \leq c \leq C = 6$ です。
島 $1$ から島 $N = 4$ に移動するには、島 $1$ と島 $2$ を結ぶ橋 $1$ を渡ってから島 $2$ と島 $4$ を結ぶ橋 $3$ を渡るか、島 $1$ と島 $3$ を結ぶ橋 $2$ を渡ってから島 $3$ と島 $4$ を結ぶ橋 $4$ を渡れば良いです。前者の経路では橋 $1$ を渡るために通行料を $\lfloor \frac{c}{3} \rfloor + 2$ 支払う必要があり、残額を $c'$ と置くと橋 $3$ を渡るために通行料を更に $\lfloor \frac{c'}{3} \rfloor + 1$ 支払う必要があります。後者の経路では橋 $2$ を渡るために通行料を $\lfloor \frac{c}{3} \rfloor + 1$ 支払う必要があり、残額を $c'$ と置くと橋 $4$ を渡るために通行料を更に $\lfloor \frac{c'}{2} \rfloor + 1$ 支払う必要があります。
$c = 1$ の時、前者の経路では $\lfloor \frac{c}{3} \rfloor + 2 = 2 > c$ なので橋 $1$ を渡れません。後者の経路では $\lfloor \frac{c}{2} \rfloor + 1 = 1 = c$ なので橋 $2$ を渡ることができますが、島 $3$ に移動した時点での所持金が $c' = c - 1 = 0$ になり、$\lfloor \frac{c'}{2} \rfloor + 1 = 1 > c'$ なので橋 $4$ を渡れません。いずれの経路でも島 $4$ に移動できません。
$c = 2$ の時、前者の経路では $\lfloor \frac{c}{3} \rfloor + 2 = 2 = c$ なので橋 $1$ を渡ることができますが、島 $2$ に移動した時点での所持金が $c' = c - 2 = 0$ になり、$\lfloor \frac{c'}{3} \rfloor + 1 = 1 > c'$ なので橋 $3$ を渡れません。後者の経路では $\lfloor \frac{c}{2} \rfloor + 1 = 2 = c$ なので橋 $2$ を渡ることができますが、島 $3$ に移動した時点での所持金が $c' = c - 2 = 0$ になり、$\lfloor \frac{c'}{2} \rfloor + 1 = 1 > c'$ なので橋 $4$ を渡れません。いずれの経路でも島 $4$ に移動できません。
$c = 3$ の時、前者の経路では $\lfloor \frac{c}{3} \rfloor + 2 = 3$ なので橋 $1$ を渡ることができ、島 $2$ に移動した時点での所持金が $c' = c - 3 = 0$ になり、$\lfloor \frac{c'}{3} \rfloor + 1 = 1 > c'$ なので橋 $3$ を渡ることができません。後者の経路では $\lfloor \frac{c}{2} \rfloor + 1 = 2 < c$ なので橋 $2$ を渡ることができ、島 $3$ に移動した時点での所持金が $c' = c - 2 = 1$ になり、$\lfloor \frac{c'}{2} \rfloor + 1 = 1 = c'$ なので橋 $4$ を渡ることができ、島 $4$ に移動した時点での所持金が $c' - 1 = 0$ になります。これより多い所持金を持って島 $4$ に移動することはできません。
$c = 4$ の時、前者の経路では $\lfloor \frac{c}{3} \rfloor + 2 = 3 < c$ なので橋 $1$ を渡ることができ、島 $2$ に移動した時点での所持金が $c' = c - 3 = 1$ になり、$\lfloor \frac{c'}{3} \rfloor + 1 = 1 = c'$ なので橋 $3$ を渡ることができ、島 $4$ に移動した時点での所持金が $c' - 1 = 0$ になります。後者の経路では $\lfloor \frac{c}{2} \rfloor + 1 = 3 < c$ なので橋 $2$ を渡ることができ、島 $3$ に移動した時点での所持金が $c' = c - 3 = 1$ になり、$\lfloor \frac{c'}{2} \rfloor + 1 = 1 = c'$ なので橋 $3$ を渡ることができ、島 $4$ に移動した時点での所持金が $c' - 1 = 0$ になります。従って前者の経路と後者の経路で残る金額は同じです。これより多い所持金を持って島 $4$ に移動することはできません。
$c = 5$ の時、前者の経路では $\lfloor \frac{c}{3} \rfloor + 1 = 3 < c$ なので橋 $1$ を渡ることができ、島 $2$ に移動した時点での所持金が $c' = c - 3 = 2$ になり、$\lfloor \frac{c'}{3} \rfloor + 1 = 1 < c'$ なので橋 $3$ を渡ることができ、島 $4$ に移動した時点での所持金が $c' - 1 = 1$ になります。後者の経路では $\lfloor \frac{c}{2} \rfloor + 1 = 3 < c$ なので橋 $2$ を渡ることができ、島 $3$ に移動した時点での所持金が $c' = c - 3 = 2$ になり、$\lfloor \frac{c'}{2} \rfloor + 1 = 2 = c'$ なので橋 $3$ を渡ることができ、島 $4$ に移動した時点での所持金が $c' - 2 = 0$ になります。従って前者の経路の方が多く所持金を残せます。これより多い所持金を持って島 $4$ に移動することはできません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。