Train Ride II
Prereq: Train Ride
You have carefully planned out the train route of the lowest ticket price, but you forgot one important fact -- are you going to make it to work on time? After considering this, you hurry to change your plan as now you need to not only 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 a time, the time it takes to ride between those 2 stations, and the ticket price of the connection.
The new input format is as follows,
The first input still denotes n the number of stations.
The second input still denotes k the number of lines.
The third input now denotes t the time that you need to be at station n by starting at station 1 in minutes.
The fourth input is the list of connections. Each connection now has four values. The first 2 values are the stations on the connection, 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 such that you can make it to 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.