PROBLEM STATEMENT
In some country there are n cities numbered from 1 to n. There are also several types of flights
between them. Each flight type is characterized with 5 integers A, B, F, T and P. All flights of
this type depart from city A and arrive at city B (without changing planes in any intermediate
cities). Each flight type is one-directional, so it is impossible to fly from city B to city A
using the same flight type. All flights of the same type depart with some periodicity. More
precisely, the first flight of this type departs from A at time F, the next flight departs at time
F + P, then at F + 2P, and so on (there are infinitely many flights of the same type). Each flight
of the same type has the same flight time T. I.e., if a plane departs from A at time T0, then it
arrives to B at time T0 + T.
The description of all flight types is given in vector flights. Concatenate the elements
of this vector in the same order as they are given without any delimiters between its
elements to get a single string. This string will contain a single space separated list of flight
type descriptions. Each such description will be of the form "A,B,F,T,P" (quotes for clarity),
where the meaning of integers A, B, F, T and P is exactly the same as defined in the previous
paragraph.
John would like to travel from city 1 to city n where his friend Brus is waiting for him.
Unfortunately, there are no direct flights from 1 to n, so he will have to use several flights to
reach city n. He can't use any other transport besides planes, so the departure city of each next
flight he takes must be the same as the arrival city of the previous flight he has taken.
Moreover, in order for him to be able to change planes, the departure time of each next flight
must be strictly greater than the arrival time of the previous flight. If he arrives at some city
at time T1 and then departs at time T2, the waiting time in this city is equal to T2 - T1. John
defines the safety of his route from 1 to n as the minimum of waiting times over all cities where
he changes flights.
John wants to arrive at city n no later than at time moment time. If there are several routes that
achieve this goal, he wants to choose the route among them with the maximum possible safety.
Return this maximum possible safety. If there are no such routes, return -1.
DEFINITION
Class:TheAirTripDivOne
Method:find
Parameters:int, vector , int
Returns:int
Method signature:int find(int n, vector flights, int time)
CONSTRAINTS
-n will be between 3 and 477, inclusive.
-flights will contain between 1 and 47 elements, inclusive.
-Each element of flights will contain between 1 and 47 characters, inclusive.
-The concatenation of all elements of flights will be a single space separated list of flight type
descriptions without leading or trailing spaces.
-Each flight type description will be of form "A,B,F,T,P" (quotes for clarity), where A, B, F, T
and P are integers formatted with no extra leading zeros.
-In each flight type, A and B will be distinct integers between 1 and n, inclusive.
-In each flight type, F, T and P will be between 1 and 1,000,000,000, inclusive.
-There will be no flight from city 1 to city n.
-time will be between 1 and 1,000,000,000, inclusive.
EXAMPLES
0)
3
{"1,2,1,4,7 ", "2,3,9,1,10"}
20
Returns: 14
The optimal way is to take the first flight at time 1 and the second one at time 19.
1)
3
{"1,2,1,1,1 2,3,2,1,98"}
100
Returns: -1
Since John needs a strictly positive time to change a flight, it is possible to get to city 3 only
at time 101.
2)
477
{"47,74,1,1,1"}
20
Returns: -1
It is impossible to reach the destination at all.
3)
7
{"1,3,15,17,11 1,3,14,16,14 5,7,12,18,18 1,6,13,1",
"6,12 1,2,18,14,13 5,6,10,10,18 3,1,10,10,10 1,3",
",17,16,10 2,3,16,18,16 6,1,15,12,10 2,1,15,18,1",
"0 4,7,10,16,15 6,3,10,14,10 1,6,19,19,15 1,4,12",
",10,14 4,7,10,18,14 2,3,16,12,12 1,3,14,10,19 3",
",7,17,10,12 2,1,14,12,16 4,3,19,11,12 1,6,10,18",
",12 2,3,16,12,10 6,2,10,18,12 5,1,14,18,12 5,1,",
"18,10,10 3,2,19,15,10 7,4,16,19,14 6,3,16,12,10",
" 5,7,14,13,13 1,3,12,10,16 5,7,16,18,15 6,2,18,",
"12,14 3,2,10,18,16 4,2,18,18,14 1,5,10,18,16 2,",
"3,10,19,16 1,4,11,18,15 2,1,15,15,14 7,2,10,12,",
"10"}
74
Returns: 33
Note that there can be multiple flight types with the same departure city and the same arrival city.
4)
7
{"1,4,10,8,2 4,6,14,8,2 6,2,8,1",
"0,1 2,7,19,5,1 ",
"1,5,15,17,11 5,3,10,1",
"0,18 3,7,12,18,18"}
147
Returns: 35
Take the flight from city 1 to city 4 at time 10 to arrive at city 4 at time 18. Then take the
flight from city 4 to city 6 at time 54 to arrive at city 6 at time 62. Next take the flight from
city 6 to city 2 at time 97 to arrive at city 2 at time 107. Finally, take the flight from city 2
to city 7 at time 142 to arrive at city 7 exactly at time 147. The safety of this route is min{54
- 18, 107 - 62, 142 - 107} = 35.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.