問題一覧 > 通常問題

No.654 Air E869120

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 137
作問者 : e869120 / テスター : square1001
9 ProblemId : 2027 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-02-23 22:37:23

問題文

"Air E869120" という航空会社は、毎日 M 個の飛行機の便を yuki 国内で運行します。
yuki 国は 街 1, 2, 3, ..., N の N 個の街から成り、i 個目の飛行機は、街 ui から vi まで飛び、時刻 pi に出発地を離陸し、時刻 qi に目的地に着陸します。また、この飛行機には wi 人乗ることができます。

2018/11/01 から、街 1 にある学校で 街 N での修学旅行が行われる予定です。
偶然、2018/11/01 の飛行機は全部空席ですが、それ以降の予約できる飛行機は全部満席です。また、この学校の校長は "Air E869120" という航空会社以外信頼していないので、この航空会社の飛行機以外使うことは出来ません。

その時、最大で何人の生徒が修学旅行に行けるか、求めなさい。
ただし、生徒は時刻 0 に離陸する飛行機に乗ることは可能であり、一日の終わり (時刻 109) に街 N の空港にいれば良いものとします。また、生徒は乗り継ぎに時間がかかるので、前の飛行機の着陸時刻と次の飛行機の離陸時刻の間に d 分以上開ける必要があります。学校の生徒は十分に多いので、無限人いると仮定してもよいです。

入力

N M d
u1 v1 p1 q1 w1
u2 v2 p2 q2 w2
u3 v3 p3 q3 w3
......
uM vM pM qM wM

制約

  • 2≤N≤1000
  • 1≤M≤1000
  • 1≤d≤109
  • 1≤ui,vi≤N,ui≠vi
  • 0≤pi<qi≤109
  • 1≤wi≤109

出力

修学旅行で移動できる最大の人数を 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もしくは右上の雲マークをクリックしてアカウントを作成してください。