TimeTravellingGogo
SRM 492 · 2010-03-12 · by dolphinigle
SRM 492 · 2010-03-12 · by dolphinigle · Graph Theory
Problem Statement
Problem Statement
Gogo lives in Rainyland and wants to attend a party. There are N houses in Rainyland, conveniently numbered 0 through N-1. Gogo lives in house 0 and the party is in house N-1. There are several bidirectional roads of various lengths that Gogo can traverse.
It rains a lot in Rainyland. In fact, with the exception of several sunny intervals, it rains all the time. The i-th sunny interval starts at the beginning of minute sunnyStart[i] and ends at the beginning of minute sunnyEnd[i]. Gogo can't get his party clothes wet, so whenever it is raining, he must be inside a house. He can only traverse roads during sunny intervals. More exactly, if he starts traversing a road at the beginning of minute A and ends at the beginning of minute B, there must exist such i that sunnyStart[i] <= A < B <= sunnyEnd[i].
The roads are given in theString[] roads. Concatenate the elements of roads to get a single space separated list of roads. Each road is formatted "a,b,travelcost" (quotes for clarity), which means that the bidirectional road connects city a and city b, and requires travelcost minutes to traverse either way.
Gogo also has a time machine, which he can use to go back in time. He can only use the time machine inside a house, and it requires machineStartTime + X minutes to go back in time by X minutes. He can go back as far as time 0, but no further. For example, suppose the time is currently 100, machineStartTime is 10, and he wants to go back to time 80 because it was sunny then. It will take him 10 + 20 = 30 minutes to get back to time 80. Note that when he uses the time machine, his position will not change. In other words, he won't go back to where he happened to be at time 80 the last time he was there.
Gogo is initially in his house at the beginning of minute 0. Return the minimum number of minutes Gogo needs to reach house N-1 without getting wet. Return -1 if it's impossible. Note that Gogo does not have to be in constant motion. For example, he can wait inside a house while waiting for a sunny interval. Also, note that time travel does not affect Gogo's total time. For example, in the scenario described above, if he used the time machine for the first time at time 100, then when he goes back to time 80, his total time will be 130 minutes, not 80 minutes.
It rains a lot in Rainyland. In fact, with the exception of several sunny intervals, it rains all the time. The i-th sunny interval starts at the beginning of minute sunnyStart[i] and ends at the beginning of minute sunnyEnd[i]. Gogo can't get his party clothes wet, so whenever it is raining, he must be inside a house. He can only traverse roads during sunny intervals. More exactly, if he starts traversing a road at the beginning of minute A and ends at the beginning of minute B, there must exist such i that sunnyStart[i] <= A < B <= sunnyEnd[i].
The roads are given in the
Gogo also has a time machine, which he can use to go back in time. He can only use the time machine inside a house, and it requires machineStartTime + X minutes to go back in time by X minutes. He can go back as far as time 0, but no further. For example, suppose the time is currently 100, machineStartTime is 10, and he wants to go back to time 80 because it was sunny then. It will take him 10 + 20 = 30 minutes to get back to time 80. Note that when he uses the time machine, his position will not change. In other words, he won't go back to where he happened to be at time 80 the last time he was there.
Gogo is initially in his house at the beginning of minute 0. Return the minimum number of minutes Gogo needs to reach house N-1 without getting wet. Return -1 if it's impossible. Note that Gogo does not have to be in constant motion. For example, he can wait inside a house while waiting for a sunny interval. Also, note that time travel does not affect Gogo's total time. For example, in the scenario described above, if he used the time machine for the first time at time 100, then when he goes back to time 80, his total time will be 130 minutes, not 80 minutes.
Constraints
- N will be between 2 and 20, inclusive.
- sunnyStart will contain between 1 and 20 elements, inclusive.
- Each element of sunnyStart will be between 0 and 999,999,999, inclusive.
- sunnyEnd will contain the same number of elements as sunnyStart.
- sunnyEnd[i] will be between sunnyStart[i]+1 and 1,000,000,000, inclusive.
- There will be at least a minute of rain between two sunny intervals, that is, sunnyEnd[i] < sunnyStart[i+1].
- roads will contain between 1 and 50 elements, inclusive.
- Each element of roads will contain between 1 and 50 characters, inclusive.
- Each character in roads will be '0'-'9', ' ', or ','.
- roads will be formatted as described in the problem statement without leading or trailing spaces.
- All integers in the concatenation of all the elements of roads in the order they are given will have no extra leading zeroes.
- In each road, a and b as described in the problem statement will be different and will each be between 0 and N-1, inclusive.
- In each road, travelcost as described in the problem statement will be between 1 and 1,000,000,000, inclusive.
- For each two different houses, there will be at most one road connecting them.
- machineStartTime will be between 1 and 1,000,000,000, inclusive.
Examples
0)
3
{0,8}
{4,12}
{"0,1,3 1,2,3"}
1
Returns: 9
First, walk from house 0 to house 1, arriving at minute 3. Then, go back in time to minute 1. This time travel requires 1+2=3 minutes. Finally, walk 3 minutes from house 1 to house 2, arriving at minute 4. The total time is 3+3+3=9 minutes.
1)
3
{0,8}
{4,12}
{"0,1,3 1,2,4"}
18
Returns: 12
First, walk from house 0 to house 1, arriving at minute 3. Then, wait inside house 1 for 5 minutes. Finally, walk 4 minutes from house 1 to house 2, arriving at minute 12. The total time is 3+5+4=12 minutes.
2)
2
{1,3}
{2,4}
{"0,1,2"}
1
Returns: -1
The length of each sunny interval is 1 minute, but the road from house 0 to house 1 requires 2 minutes to traverse, so it is impossible for Gogo to arrive at the party without getting his clothes wet.
3)
3
{0,17}
{15,37}
{"0,1,1","5"," 1,2,12 2,0,17"}
10
Returns: 29
4)
20
{0,5000000,10000000,15000000,20000000,
25000000,30000000,35000000,40000000,45000000,
100000000,250000000,500000000,500000005,500000010,
500000200,501000000,550000000,570000000,600000000}
{
4000000,9000000,13000000,16000000,21000000,
29000000,34000000,38000000,43000000,45050000,
160000000,450000000,500000001,500000009,500000110,
500500200,507000000,560000000,590000000,1000000000}
{"0,1,200000000 1,2,200000000 2,3,200000000 ",
"3,4,200000000 4,5,200000000 5,6,200000000 ",
"6,7,200000000 7,8,200000000 8,9,200000000 ",
"9,10,200000000 10,11,200000000 11,12,200000000 ",
"12,13,200000000 13,14,200000000 14,15,200000000 ",
"15,16,200000000 16,17,200000000 17,18,200000000 ",
"18,19,200000000"}
100000000
Returns: 8200000000
Submissions are judged against all 124 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TimeTravellingGogo with a public method long long determineTime(int N, vector<int> sunnyStart, vector<int> sunnyEnd, vector<string> roads, int machineStartTime) · 124 test cases · 2 s / 256 MB per case