767. Coupon Road Trip
A delivery van travels between n towns numbered 0 to n - 1. Each entry [a, b, toll] of edges is a two-way road between towns a and b with a toll of toll coins. The van starts in town 0 and must finish in town n - 1.
The driver holds k half-price coupons. Each coupon can be used once, on a single road crossing, and turns that crossing's toll into floor(toll / 2); at most one coupon applies to one crossing. Return the minimum total toll to get from town 0 to town n - 1 using at most k coupons, or -1 if the final town cannot be reached.
Example 1
- Input:
- n = 4edges = [[0,1,10],[1,3,10],[0,2,3],[2,3,30]]k = 1
- Output:
- 15
- Explanation:
Take 0-1-3 and spend the coupon on the first road (10 becomes 5): 5 + 10 = 15, cheaper than 0-2-3 at 3 + 15 = 18.
Example 2
- Input:
- n = 2, edges = [[0,1,7]], k = 1
- Output:
- 3
- Explanation:
The only road costs 7; with the coupon it costs floor(7 / 2) = 3.
Example 3
- Input:
- n = 3, edges = [[0,1,5]], k = 2
- Output:
- -1
- Explanation:
City 2 cannot be reached from city 0, so the answer is -1.
Constraints
- 2 ≤ n ≤ 104
- 1 ≤ edges.length ≤ 5 * 104
- 0 ≤ a, b < n, a ≠ b
- 1 ≤ toll ≤ 104
- 0 ≤ k ≤ 20
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m * k * log(n * k))
- Space
- O(n * k + m)