Train delays
Time Limit: 10 Seconds Memory Limit: 65536 KB
Last year, some of the judges tried to travel to NWERC’10 by train. This turned into a big disaster: on the way there, a fire in a control room caused huge delays, while on the return trip, trains in Bremen were delayed due to a terrorist threat in Hamburg. Of course, these huge delays caused other delays in the train schedule, so the big question was which trains
to take: would it be better to take this slow regional train now, or wait for that intercity train, which has a big chance of being delayed?
This year, the judges have planned ahead and carefully analyzed the train schedule. They even kept track of how often trains were delayed and by how much. Now that they have all this information, they want to travel as quickly possible, minimizing the expected duration of the journey. Can you help them?
For each train connection, the judges know exactly what its scheduled departure time and duration are, as well as the probability that its arrival at the destination will be delayed. You may assume that the probabilities of delays are independent and that the judges can adapt their itinerary as they go, depending on any delays which they might already have incurred.
Trains always depart on time, but may arrive late and the judges do not know whether a train’s arrival will be delayed until they have boarded it. It takes judges no time to switch trains, so they can take a connecting train that departs at the same time as they arrive at a place.
The judges can choose the time of their initial departure as they wish and they want to minimize the expected duration of their total trip.
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
• one line with the judges’ place of origin and destination, these are different.
• one line with an integer n (1 ≤ n ≤ 1 000): the number of train connections.
• n lines, each describing a train connection:
– the origin and destination of this connection, these are different.
– an integer m (0 ≤ m ≤ 59), the departure time in minutes after each full hour.
– an integer t (1 ≤ t ≤ 300), the standard journey time (assuming no delays).
– an integer p (0 ≤ p ≤ 100), the probability of delays as a percentage.
– an integer d (1 ≤ d ≤ 120), the maximum delay in minutes.
All place names are given as strings of upper and lower case alphabetical characters, of length at most 20. If a train is delayed, then the length of the delay will be a whole number of minutes, and will be uniformly distributed in the range [1, d].
Output
Per test case:
• one line with a floating point number: the minimum expected duration of the total trip in minutes.
This number should be accurate up to 10−6 relative or absolute precision. Output IMPOSSIBLE instead if the destination is not reachable.
Sample Input
3 Hamburg Bremen 3 Hamburg Bremen 15 68 10 5 Hamburg Bremen 46 55 50 60 Bremen Frankfurt 14 226 10 120 Amsterdam Rotterdam 1 Amsterdam Utrecht 10 22 5 10 BremenVegesack Utrecht 9 BremenVegesack BremenHbf 15 10 0 1 BremenVegesack BremenHbf 45 10 0 1 BremenVegesack Leer 23 140 10 15 BremenHbf Osnabruck 44 51 60 70 Osnabruck Amersfoort 55 147 38 40 Amersfoort Utrecht 24 15 30 15 Amersfoort Utrecht 54 15 10 35 Leer Groningen 45 140 5 10 Groningen Amersfoort 46 96 10 20
Sample Output
68.3 IMPOSSIBLE 305.0532857Submit
Source: NWERC 2011