n cities numbered 0 to n - 1, linked by toll roads: roads[i] = [a, b, toll] means there is a two-way road between cities a and b that costs toll to drive along.
You hold coupons coupons. Showing a coupon on a road cuts its toll to toll // 2 (rounded down). Each coupon works once, and at most one coupon can be used per road trip.
Return the least amount you have to pay to get from city 0 to city n - 1, or -1 if it cannot be reached.n=4, roads=[[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 19]], coupons=1 → 12
Via city 2: 3 + 19 // 2 = 3 + 9 = 12. Via city 1: 10 + 10 // 2 = 15. The answer is 12.
n=3, roads=[[0, 1, 7], [1, 2, 5]], coupons=5 → 5
There are enough coupons for both roads: 7 // 2 + 5 // 2 = 3 + 2 = 5.
n=3, roads=[[0, 1, 4]], coupons=2 → -1
No road leads to city 2, so the answer is -1.
n=4, roads=[[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 19]], coupons=1
12
Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.