n перекрёстков с номерами от 0 до n - 1 и односторонние дороги: roads[i] = [from, to, cost] означает дорогу из from в to, аренда которой стоит cost. Между одной парой перекрёстков может быть несколько дорог.
На перекрёстках depot_a и depot_b стоят два склада, на перекрёстке client — клиент. Нужно арендовать набор дорог так, чтобы по арендованным дорогам из каждого склада можно было доехать до клиента. Одну и ту же дорогу оба склада могут использовать, а платить за неё нужно один раз.
Верните наименьшую суммарную стоимость аренды или -1, если подходящего набора дорог не существует.n=4, roads=[[0, 2, 3], [1, 2, 4], [2, 3, 1], [0, 3, 10]], depot_a=0, depot_b=1, client=3 → 8
Арендуем дороги 0 → 2, 1 → 2 и 2 → 3: оба склада сходятся в узле 2 и дальше пользуются общей дорогой до клиента. 3 + 4 + 1 = 8.
n=3, roads=[[0, 2, 5]], depot_a=0, depot_b=1, client=2 → -1
Из склада 1 не выходит ни одной дороги, до клиента ему не добраться.
n ≤ 10⁵roads.length ≤ 10⁵roads[i].length = 3from, to, depot_a, depot_b, client ≤ n - 1from ≠ todepot_a, depot_b и client попарно различныcost ≤ 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
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 60 тестов на сервере, включая скрытые.