EASY
Nothing really special here. Let t _ i be the earliest time we can arrive at station i with the base case t _ 0 = 0. Then given t _ i we can easily compute t _ {i+1} by waiting from time t _ i until the next train departs from station i, and then adding the travel time to this departure time to get t _ {i+1}.
Can be found here.
Can be found here.
Algorithm is simple :
pick up earliest trains from each station that will give minimum time. Now why ???
The reason is : let us say there be different path of choosing time of trains from each station . let this gives us minimum time to reach final end destination.Let’s say for station si , we have time ti + kfi in our path of minimum time. Then if we can reach time slots that are available to us for station si less than ti + kfi that to will also lead us to shortest time also.
Hence only earliest time slots that we can reach for catching trains are sufficient enough to reach in minimum time possible.