Catch the Plane

This problem asks gives us a bus schedule, where each bus has a probability of ACTUALLY running, and then asks us to figure out the max probability we can arrive at a given node before a given time.

Standard problems might ask us to optimize for the probability of ever reaching a given location, or the minimum time it takes to get there, but attempting to do both at the same time makes this slightly more difficult. A way to fix this might be to use a dp:

dp[node][time] = maximum probability of getting to node at time

or swapping the dimensions

dp[node][probability] = minimum time of getting to a node with at least a given probability

The issue with the first one is time is 10^18. Even with Category:Interesting Points or