No.654 Air E869120
タグ : / 解いたユーザー数 130
作問者 :
e869120
/ テスター :
square1001
問題文
"Air E869120" という航空会社は、毎日 $M$ 個の飛行機の便を yuki 国内で運行します。
yuki 国は 街 $1$, $2$, $3$, ..., $N$ の $N$ 個の街から成り、$i$ 個目の飛行機は、街 $u_i$ から $v_i$ まで飛び、時刻 $p_i$ に出発地を離陸し、時刻 $q_i$ に目的地に着陸します。また、この飛行機には $w_i$ 人乗ることができます。
2018/11/01 から、街 $1$ にある学校で 街 $N$ での修学旅行が行われる予定です。
偶然、2018/11/01 の飛行機は全部空席ですが、それ以降の予約できる飛行機は全部満席です。また、この学校の校長は "Air E869120" という航空会社以外信頼していないので、この航空会社の飛行機以外使うことは出来ません。
その時、最大で何人の生徒が修学旅行に行けるか、求めなさい。
ただし、生徒は時刻 $0$ に離陸する飛行機に乗ることは可能であり、一日の終わり (時刻 $10^9$) に街 $N$ の空港にいれば良いものとします。また、生徒は乗り継ぎに時間がかかるので、前の飛行機の着陸時刻と次の飛行機の離陸時刻の間に $d$ 分以上開ける必要があります。学校の生徒は十分に多いので、無限人いると仮定してもよいです。
入力
$N$ $M$ $d$ $u_1$ $v_1$ $p_1$ $q_1$ $w_1$ $u_2$ $v_2$ $p_2$ $q_2$ $w_2$ $u_3$ $v_3$ $p_3$ $q_3$ $w_3$ ...... $u_M$ $v_M$ $p_M$ $q_M$ $w_M$
制約
- $2 \le N \le 1000$
- $1 \le M \le 1000$
- $1 \le d \le 10^9$
- $1 \le u_i, v_i \le N, u_i ≠ v_i$
- $0 \le p_i < q_i \le 10^9$
- $1 \le w_i \le 10^9$
出力
修学旅行で移動できる最大の人数を 1 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 2 5 1 2 0 25 10 1 2 10 40 5
出力
15
飛行機 $1$ を使って $10$ 人、飛行機 $2$ を使って $5$ 人輸送できるので、合計で $10+5=15$ 人修学旅行に行くことができます。
サンプル2
入力
4 5 5 1 2 0 15 40 1 3 5 20 10 2 3 30 40 20 2 4 50 80 20 3 4 50 70 30
出力
50
$20$ 人が $1$->$2$->$4$ というルートをたどり、$20$ 人が $1$->$2$->$3$->$4$ というルートをたどり、$10$ 人が $1$->$3$->$4$ というルートをたどれば $50$ 人の輸送は可能です。
サンプル3
入力
3 4 5 1 2 0 10 10 1 2 10 20 3 2 3 15 25 2 2 3 5 15 10
出力
2
飛行機 $1$ -> 飛行機 $3$ というルート以外、乗り継ぎの関係上使うことができません。
サンプル4
入力
4 3 5 1 2 0 10 100 2 3 15 31 100 3 4 35 45 100
出力
0
残念ながら、この例では $1$ 分差で飛行機 $2$ から $3$ に乗り継ぐことができません。
サンプル5
入力
4 40 9 2 3 90 99 43 2 3 12 60 56 1 3 5 9 30 4 3 76 96 88 2 4 76 86 66 1 2 36 91 5 2 1 23 82 87 1 4 66 83 12 1 2 2 33 72 4 1 2 90 30 3 2 32 84 25 4 2 13 99 56 4 3 49 56 94 1 3 29 42 31 1 2 86 88 93 3 4 43 51 28 3 4 5 69 60 3 1 3 4 39 1 4 7 73 99 3 2 31 85 94 1 2 89 94 94 2 1 34 70 62 3 4 39 94 63 4 1 23 30 96 3 4 41 81 29 4 3 57 62 48 3 2 33 54 27 3 1 44 73 44 3 2 50 70 19 4 2 19 36 82 4 2 95 97 94 3 4 20 58 10 1 4 4 97 33 2 3 46 58 58 3 1 0 80 45 4 1 1 76 43 3 2 16 97 9 3 1 13 16 45 2 4 4 16 12 2 3 68 98 12
出力
240
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。