n junctions numbered from 0 to n - 1 and one-way roads: roads[i] = [from, to, cost] is a road from from to to that costs cost to rent. There may be several roads between the same pair of junctions.
Two depots stand at junctions depot_a and depot_b, and a client is at junction client. You need to rent a set of roads so that the client can be reached from each depot using rented roads only. Both depots may use the same road, and it is paid for only once.
Return the smallest total rental cost, or -1 if no suitable set of roads exists.n=4, roads=[[0, 2, 3], [1, 2, 4], [2, 3, 1], [0, 3, 10]], depot_a=0, depot_b=1, client=3 → 8
Rent the roads 0 → 2, 1 → 2 and 2 → 3: both depots meet at node 2 and share the last road to the client. 3 + 4 + 1 = 8.
n=3, roads=[[0, 2, 5]], depot_a=0, depot_b=1, client=2 → -1
No road leaves depot 1, so it can never reach the client.
n ≤ 10⁵roads.length ≤ 10⁵roads[i].length = 3from, to, depot_a, depot_b, client ≤ n - 1from ≠ todepot_a, depot_b and client are pairwise distinctcost ≤ 10⁵n=4, roads=[[0, 2, 3], [1, 2, 4], [2, 3, 1], [0, 3, 10]], depot_a=0, depot_b=1, client=3
8
Run checks the first 3 tests in your browser. Submit checks all 60 tests on the server, hidden ones included.