Train Ride II
Prereq: Train Ride
You have carefully planned out the train route with the lowest ticket price, but you forgot one important fact—will you make it to work on time? After considering this, you hurry to change your plan as now you not only need to buy the cheapest ticket but also make sure you get to work on time. You quickly whip out your map and mark each connection in the subway with the time it takes to travel between those 2 stations, and the ticket price of the connection.
The new input format is as follows:
The first input still represents n as the number of stations.
The second input still represents k as the number of lines.
The third input now represents t as the time by which you need to be at station n, starting from station 1, in minutes.
The fourth input is the list of connections. Each connection now includes four values. The first 2 values are the stations connected, the 3rd value is the line number that the connection belongs to, and the 4th value is the time needed to traverse this connection in minutes.
Return the lowest ticket cost that allows you to arrive at work on time. Return -1 if no such ticket can be bought to get you to work on time.
Examples
Example 1:
Input:
n = 5, k = 2, t = 6, connections = [[1, 2, 1, 1], [2, 3, 1, 2], [3, 4, 1, 3], [4, 5, 1, 4], [1, 5, 2, 6]]
Output:
2
Explanation:
If you only use the connections on line 1 there exists a path to your workplace but you will be late to work.
The total time would be 1 + 2 + 3 + 4 = 10 minutes but you only have 6 minutes.
By buying a ticket with price 2 you can take the connection [1, 5, 2, 6] which will take only 6 minutes and therefore allow you to arrive at work on time.