All submissions for this problem are available.
According to many researches, people can stand on a bus for several hours, but waiting for a bus for more than 30 minutes at a bus station can make us exhausted. The Chef is a perfect example for this fact. He always tries to reduce the longest period of time of waiting for a bus. Therefore, optimizing the traveling plan for him is far from an easy task.
Let's consider the bus system with N bus stations (numbered from 1 to N) and M buses (numbered from 1 to M). Each bus is represented by 4 integer numbers U, V, S, E which means it will start at the bus station U at the time S and arrive at the bus station V at the time E with no intermediate bus stations. If passenger arrives at the bus station U at the time X ≤ S, he has to wait for S − X units of time to catch this bus. Note, that if he arrives at the bus station U exactly at time S he can catch this bus with no waiting time.
The Chef starts at the time 0 in the bus station 1, and he wants to arrive at the bus station N in a way that the longest period that he spends for waiting for a bus is as small as possible. Besides, he must be at the bus station N before or at the time T for a specially important meeting. Note, that he may wait for a meeting if he arrives at the bus station N early but that period is not our concern here, since he doesn't wait for any bus at that time.
The first line of the input contains three space-separated integers N, T and M, denoting the number of bus stations, the deadline for coming to bus station N and the number of buses, respectively. Each of the following M lines contains four space-separated integers U, V, S, E, the parameters of the current bus as described in the problem statement.
If Chef cannot arrive at the bus station N before or at the time T, output -1. Otherwise, output the maximum period of time he has to wait for a bus in the optimal traveling plan.
- 2 ≤ N ≤ 50000
- 1 ≤ T ≤ 109
- 1 ≤ M ≤ 100000 (105)
- 1 ≤ U ≤ N
- 1 ≤ V ≤ N
- U ≠ V
- 0 ≤ S < E ≤ 109
Input: 5 10 5 1 2 1 2 1 5 3 4 2 4 4 5 2 5 5 6 4 5 6 7 Output: 2
There are three different traveling plans:
- bus 1 → bus 3 → bus 5. His waiting time for each bus is 1, 2, 1, respectively.
- bus 2. His waiting time is 3.
- bus 1 → bus 4. His waiting time for each bus is 1, 3, respectively.
For each traveling plan Chef arrives at the bus station N = 5 before the time T = 10. But only the first traveling plan is optimal, since the longest period of time his has to wait is 2.
|Tags||binary-search, cook32, dynamic-programming, easy-medium, graph, tuananh93|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.