n cities numbered 0 to n - 1, all connected by a network of two-way roads. Road roads[i] = [x, y, t] links cities x and y and takes t minutes. Two cities may be linked by several roads with different times, but no road leads from a city to itself.
Every time you are in city j you pay a toll of fees[j] (the start and end cities included; visiting a city again means paying again).
You start in city 0 and must reach city n - 1 within deadline minutes. Return the minimum total toll for such a trip, or -1 if it cannot be done in time.deadline=10, roads=[[0, 1, 2], [1, 3, 2], [0, 2, 4], [2, 3, 4]], fees=[1, 9, 2, 3] → 6
Going through city 2 takes 8 minutes and costs 1 + 2 + 3 = 6; through city 1 it takes 4 minutes but costs 1 + 9 + 3 = 13. Both are on time, so the cheaper one wins: 6.
deadline=5, roads=[[0, 1, 2], [1, 3, 2], [0, 2, 4], [2, 3, 4]], fees=[1, 9, 2, 3] → 13
Now the route through city 2 (8 minutes) is too slow, so only the route through city 1 remains, at 13.
deadline=3, roads=[[0, 1, 4]], fees=[2, 2] → -1
The only road takes 4 minutes, which is too long.
deadline ≤ 1000fees) ≤ 1000roads) ≤ 1000fees[j] ≤ 1000deadline=10, roads=[[0, 1, 2], [1, 3, 2], [0, 2, 4], [2, 3, 4]], fees=[1, 9, 2, 3]
6
Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.