There are N towns, and M one-way direct bus routes (no intermediate stops) between them. The towns are numbered from 1 to N. A traveler who is located in the town 1 at time 0 needs to arrive in the town P. He will be picked from the bus station at town P exactly at time T. If he arrives earlier he will have to wait.
For each bus route i, we know the source and destination towns si and ti, of course. We also know the departure and arrival times, but only approximately: we know that the bus departs from si within the range [ai, bi] and arrives at ti within the range [ci, di] (endpoints included in both cases).
The traveler does not like waiting, and therefore is looking for a travel plan which minimizes the maximal possible waiting time while still guaranteeing that he'll not miss connecting buses (that is, every time he changes buses, the latest possible arrival of the incoming bus must not be later than the earliest possible departure time of the outgoing bus).
When counting waiting time we have to assume the earliest possible arrival time and the latest possible departure time.
Write a program to help the traveler to find a suitable plan.
입력 3 6 2 100 1 3 10 20 30 40 3 2 32 35 95 95 1 1 1 1 7 8 1 3 8 8 9 9 2 2 98 98 99 99 1 2 0 0 99 101 출력 32 The most pessimistic case for the optimal travel plan for the above example is as follows: Time Action 0…1 Wait in town 1 1…7 Take the bus line 3 from town 1 to town 1 7…8 Wait in town 1 8…9 Take the bus line 4 from town 1 to town 3 9…35 Wait in town 3 35…95 Take the bus line 2 from town 3 to town 2 95…98 Wait in town 2 98…99 Take the bus line 5 from town 2 to town 2 99…100 Wait in town 2 Total waiting time: 1+1+26+3+1=32 입력 3 2 2 100 1 3 0 0 49 51 3 2 50 51 100 100 출력 -1
출처:boi 2005