Express tokens
HardOnline Assessment
Find the fastest trip across a road network when you hold a few express tokens.
A delivery driver must travel from town 0 to town n - 1. roads lists two-way roads as [a, b, minutes]: the road connects towns a and b and takes minutes to drive in either direction. Several roads may join the same pair of towns, and the driver may pass through a town more than once.
The driver holds tokens express tokens. Presenting a token while driving along a road once cuts that drive to minutes // 2 minutes (the time is halved and rounded down, so a 7-minute road becomes 3 minutes and a 1-minute road becomes 0). A token is spent when used, only one token can be used per drive along a road, and the driver does not have to use all of them. Driving the same road again later is a new drive and needs a new token to be discounted.
Input: n, the number of towns; roads, a list of [a, b, minutes] with minutes >= 1; and tokens, a non-negative integer.
Output: an integer, the smallest total number of minutes needed to get from town 0 to town n - 1. If n is 1 the driver is already there and the answer is 0. If town n - 1 cannot be reached, return -1.
Spending tokens on the quickest route is not always best, and trying every route will be too slow on larger networks.
Example 1
- Input:
- [3,[[0,1,10],[1,2,10]],1]
- Output:
- 15
- Explanation
- The only route is 0, 1, 2. One token halves one of the two 10-minute drives, giving 10 + 5 = 15.
Example 2
- Input:
- [4,[[0,1,5],[1,2,5],[2,3,5],[0,3,16]],1]
- Output:
- 8
- Explanation
- The route 0, 1, 2, 3 takes 15 minutes, or 12 with a token on one 5-minute drive (5 becomes 2). The direct road takes 16 minutes, or 8 with the token. Spending the token on the longer road wins, so the answer is 8 even though the direct road is slower without tokens.
Example 3
- Input:
- [3,[[0,1,7],[1,2,9],[0,2,30]],2]
- Output:
- 7
- Explanation
- The route 0, 1, 2 takes 7 + 9 = 16 minutes. With two tokens it becomes 3 + 4 = 7, because 7 // 2 = 3 and 9 // 2 = 4. The direct road would cost 15 even with a token, so the answer is 7.
Constraints
1 <= n <= 1500 <= roads.length <= 600, each road is[a, b, minutes]with0 <= a, b < n,a != band1 <= minutes <= 1,0000 <= tokens <= 20