Hide

Problem H
Train Delays

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 duration1 of their total trip.

Input

  • one line with the judges’ place of origin and destination, these are different.

  • one line with an integer $n$ ($1 \leq n \leq 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\leq m\leq 59$), the departure time in minutes after each full hour.

    • an integer $t$ ($1\leq t\leq 300$), the standard journey time (assuming no delays).

    • an integer $p$ ($0\leq p\leq 100$), the probability of delays as a percentage.

    • an integer $d$ ($1\leq d\leq 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

Output 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 1 Sample Output 1
Hamburg Bremen
3
Hamburg Bremen 15 68 10 5
Hamburg Bremen 46 55 50 60
Bremen Frankfurt 14 226 10 120
68.3
Sample Input 2 Sample Output 2
Amsterdam Rotterdam
1
Amsterdam Utrecht 10 22 5 10
IMPOSSIBLE
Sample Input 3 Sample Output 3
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
305.0532857

Footnotes

  1. Given a travel plan of which trains to take (depending on previous connections and delays), the expected trip duration $E$ is defined to be the sum of the trip duration $T_ i$ for each itinerary $i$ possibly taken multiplied by the chance $p_ i$ of that itinerary occurring: $E = \sum _ i p_ i T_ i$.

Please log in to submit a solution to this problem

Log in