n cities numbered 0 to n - 1 and two-way toll roads: roads[i] = [a, b, cost] connects cities a and b, and driving along it costs cost. Every city can reach every other, there is at most one road between any two cities, and no road leads from a city to itself.
A traveller holds passes passes. A pass makes one road free, and a route may use at most passes of them.
Return the smallest amount the traveller has to pay to get from city start to city finish.n=4, roads=[[0, 1, 5], [1, 3, 5], [0, 2, 1], [2, 3, 20]], start=0, finish=3, passes=1 → 1
Without passes the best route is 0 → 1 → 3 for 10. With one pass, 0 → 2 → 3 is cheaper: pay 1 for the first road and ride the road worth 20 for free.
n=3, roads=[[0, 1, 7], [1, 2, 3]], start=0, finish=2, passes=0 → 10
There are no passes and only one route: 7 + 3 = 10.
n=5, roads=[[0, 1, 4], [1, 2, 4], [2, 3, 4], [3, 4, 4]], start=0, finish=4, passes=2 → 8
The route 0 → 1 → 2 → 3 → 4 has four roads worth 4 each; two are free, which leaves 8.
n ≤ 500roads.length ≤ min(10⁴, n·(n − 1)/2)a, b ≤ n − 1, a ≠ bcost ≤ 10⁶start, finish, passes ≤ n − 1, start ≠ finishn=4, roads=[[0, 1, 5], [1, 3, 5], [0, 2, 1], [2, 3, 20]], start=0, finish=3, passes=1
1
Run checks the first 3 tests in your browser. Submit checks all 62 tests on the server, hidden ones included.