Problem Statement |
| | You live in a big city and need to travel to work every day using the metro rail network. However, the railway lines aren't 100% reliable and occasionally problems with the track lead to a line having to run much slower than usual. You've been in the city for a while, so you know the approximate probabilities of delays happening on each of the lines. Your task is to develop a strategy that minimizes the expected time to get from your starting point to your destination.
When setting out on your journey, you have no way of telling which lines are delayed. Fortunately, the rail company posts information about delayed lines at the stations. However, they are not very good at communicating between stations, so each station will only have information posted about the train lines that pass through that particular station. You will therefore find out whether a line is delayed the first time you arrive in a station through which that line passes. Note that you have to be in the station to read the notice, so you don't gain information about delays by passing through a station on a train without disembarking. If a line is delayed, then the amount of time for the trains to run between adjacent stations on that line is increased by an amount delay. Getting on and off trains also takes a certain amount of time. You may assume that the lines which are delayed do not change throughout the course of the entire journey. Trains run in both directions on all lines, with the journey time being the same in both directions, but to change direction, you have to disembark and reboard. Assume that a delay affects trains in both directions.
Each line is given as the order of stations that the train visits on that line. A line may pass through a station multiple times, but these intersections are not joined. For example, if a train visits stations 0 1 2 3 4 5 2 6 7 in that order and you are at station 0 wishing to get to station 7, you have two options: visit all the stations on the line, or disembark at station 2 and reboard a different train at the later point on the line where it passes through station 2 again. There is no train that visits stations 0 1 2 6 7 without going through stations 3 4 5.
You will be given a String[] lines, where each element will contain a space-separated list of integers representing the stations that the a single line passes through in order, with the jth integer in the ith element being the number of the jth station on that line. The time that the trains take between each station will be described as a space-separated list of integers in a String[] times. The ith element of times describes the ith line in lines, with the jth integer being the time to travel between the jth and j+1th stations on the line. The probability of each line being delayed is given as a percentage in probabilities in the same order as lines. The time to catch or disembark a train is changeTime and the additional time to travel between adjacent stations if a line is delayed is delay.
You should work out the minimum expected journey time to get from station start to station destination and return this time. Return -1.0 if it is not possible to reach station destination from station start. |
| |
Definition |
| | | Class: | MetroNetwork | | Method: | minimizeTime | | Parameters: | int, int, String[], String[], int[], int, int | | Returns: | double | | Method signature: | double minimizeTime(int start, int destination, String[] lines, String[] times, int[] probabilities, int changeTime, int delay) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The return value must be accurate to within an absolute or relative tolerance of 1e-9. |
| - | changeTime includes the time you spend waiting for trains. |
| - | It takes changeTime time to board a train and changeTime time to disembark. For a single journey on a single line, therefore, the cost is 2 * changeTime + journey-time. |
| - | If multiple lines pass through a station, you will find out about delays on all of these lines when you are in the station. |
| |
Constraints |
| - | lines will contain between 1 and 8 elements, inclusive. |
| - | times and probabilities will contain the same number of elements as lines. |
| - | Each element of lines and times will contain no more than 50 characters. |
| - | Each element of lines will be a space-separated list of integers, without leading zeros, containing at least 2 integers. |
| - | Each integer in lines will be between 0 and 39, inclusive. |
| - | Each element of times will be a space-separated list of integers, without leading zeros, containing exactly 1 fewer integer than the corresponding element of lines. |
| - | Each integer in times will be between 1 and 100, inclusive. |
| - | Each element of probabilities will be between 0 and 100, inclusive. |
| - | changeTime will be between 1 and 100, inclusive. |
| - | delay will be between 1 and 100, inclusive. |
| - | start and destination will be distinct and will correspond to stations in lines. |
| |
Examples |
| 0) | |
| | 0 | 7 | {"0 1 2 3 4 5 6 7"} | {"2 2 2 2 2 2 2"} | {50} | 5 | 5 |
| Returns: 41.5 | 
This network is shown topologically in the above diagram. In this diagram and all subsequent ones, station numbers are shown in bold numerals and segment times are shown italicized. When there is a possibility of a line being delayed, this segment time is formatted "non-delayed time/delayed time", quotes for clarity.
Here there is a single line, so no choice as to which route to take. If the line is not delayed then the journey time is
5 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 5 = 24
If the line is delayed, the time is
5 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 5 = 59
For a total expected journey time of
0.5 * 24 + 0.5 * 59 = 41.5 |
|
|
| 1) | |
| | 0 | 3 | {"0 1","0 2","1 3","2 3"} | {"5","5","5","5"} | {0,0,50,50} | 5 | 20 |
| Returns: 40.0 | 
This network is shown above. Here you have 2 choices: you can either travel to station 1 on line zero, then change to line 2, or travel to station 2 on line 1 and change to line 3. Lines 0 and 1 are never delayed and lines 2 and 3 are delayed 50% of the time. Since you cannot tell from station 0 which of lines 2 and 3, if either, are delayed, and both of the journey times are otherwise the same, you just pick one of the choices at random. You will end up having to travel on a delayed line 50% of the time.
|
|
|
| 2) | |
| | 0 | 3 | {"0 1","0 2","0 1 3","2 3"} | {"5","5","100 5","5"} | {0,0,50,50} | 5 | 20 |
| Returns: 35.0 | 
This is the same network as example 1, except line 2 has been extended to station 0 (see diagram). The time to travel on the additional segment is way too long for you to ever bother travelling on it, but it means that line 2 passes through station 0, so you know from the start whether or not it is delayed. The optimal strategy is now to consider whether line 2 is delayed from the start at station 0. If it is, then travel to station 1 on line 0 and then to station 3 on line 2. Otherwise you should take the other route via station 2. This strategy ensures that you will only travel on a delayed line if both lines 2 and 3 are delayed (25% probability), thus leading to a reduction in the expected journey time. |
|
|
| 3) | |
| | 0 | 4 | {"0 1 2 3","1 3 4","2 4"} | {"10 10 20","100 10","80"} | {0,50,0} | 5 | 100 |
| Returns: 105.0 | 
This network is shown above. Here, the optimal strategy is to travel to station 1 on line 0 and get off purely to check whether line 1 is delayed or not. If it is, then travel to station 2 on line 0, then station 4 on line 2. Otherwise travel to station 3 on line 0 and then to station 4 on line 1. |
|
|
| 4) | |
| | 12 | 9 | {"0 30 1 2 3 4 31 5 6 7",
"38 6 8 32 9 33 10 34 11 0 12 13 14 15 16 36 5 38",
"17 39 18 19 5 8 9 20 21",
"17 39 22 16 23 24 3 25 20 21",
"28 9 20 25 2 27 14 17",
"12 13 27 26 24 4 9 28",
"29 10 1 27 15 22 19",
"11 10 2 26 23 16 22 18"} | {"3 3 2 3 2 3 2 2 5",
"2 1 3 4 3 2 4 2 4 5 1 4 4 2 4 5 4",
"2 4 4 2 2 6 2 4",
"2 8 2 1 1 2 3 1 6",
"6 1 2 2 2 2 6",
"1 7 1 2 2 4 8",
"7 2 3 2 2 4",
"4 4 2 2 1 2 9"} | {20,5,15,50,45,5,10,5} | 3 | 10 |
| Returns: 23.228506624999994 | |
|
| 5) | |
| | 0 | 3 | {"0 1","2 3"} | {"2","2"} | {50,50} | 5 | 5 |
| Returns: -1.0 | | There is no route to the destination here. |
|
|
| 6) | |
| | 31 | 8 | {"35 38 1 3 4 7 9 10 12 14 16 18 19 20 21 24 25 26"
,"7 10 11 13 15 16 19 22 23 25 26 27 30 33 35 38 1"
,"35 38 1 3 5 6 9 11 13 16 17 19 22 25 26 29 30 32"
,"24 26 28 29 32 34 37 39 1 4 6 8 11 13 16 17 18 19"
,"13 15 17 20 22 25 26 29 30 32 35 37 0 2 3 6 7 8"
,"20 22 24 26 29 31 32 33 36 38 0 3 6 8 9 12 13 14"
,"12 15 16 18 19 21 22 24 25 26 28 30 31 32 33 35"
,"32 34 37 38 39 0 2 4 7 9 12 15 17 20 22 23 24 27"} | {"2 4 9 9 4 4 2 9 7 5 8 3 3 6 7 4 1"
,"1 6 6 8 8 10 7 1 8 10 9 8 9 3 3 2"
,"2 2 7 9 9 1 9 7 9 6 4 4 1 1 10 2 3"
,"10 10 6 5 1 9 9 6 10 5 4 7 5 3 1 2 2"
,"5 1 3 9 2 5 5 6 5 6 3 5 8 8 5 1 6"
,"4 10 4 1 7 1 9 3 5 3 6 9 2 10 3 9 7"
,"9 3 6 6 6 3 5 6 10 10 2 2 5 2 6"
,"1 7 3 6 1 10 2 1 7 4 7 9 7 10 7 3 2"} | {81,5,54,32,6,12,80,38} | 4 | 88 |
| Returns: 56.38865447903488 | |
|