Editorial for UTS Open '15 #4 - Subway
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be the chance of arriving on time if you're at station with minutes left.
Let be the expected value of if you're at station with minutes left.
Let be the value of corresponding to the edge leaving station . and are defined similarly.
Let be the number of edges leaving station .
The intuitive explanation of the above is that the expected value is the weighted average of the expected value of all possible next states, weighted according to (chance of reaching next state) × (chance of being on time from that state).
This leads immediately to an solution, which can be improved to by storing the values of and with a prefix sum array.