depots складов с номерами от 0 до depots - 1, связанных двусторонними дорогами: roads[i] = [a, b, len] — дорога длины len между складами a и b. Между двумя складами может быть несколько дорог. Сейчас из любого склада можно доехать до любого другого.
Компания хочет закрыть часть складов (возможно, ни одного или все). Дороги, ведущие к закрытому складу, тоже перестают использоваться. После закрытия от каждого оставшегося склада до каждого другого оставшегося должно быть можно доехать по оставшимся дорогам, и кратчайший путь не должен быть длиннее reach.
Верните количество наборов закрываемых складов, при которых это условие выполнено.depots=3, reach=4, roads=[[0, 1, 3], [1, 2, 3]] → 6
Оставить все три нельзя: от 0 до 2 ехать 6. Закрыть только 1 тоже нельзя — 0 и 2 окажутся отрезаны. Подходят: закрыть 0, закрыть 2, любые два склада или все три — итого 6 вариантов.
depots=2, reach=5, roads=[[0, 1, 9], [0, 1, 2]] → 4
Между складами две дороги, по короткой ехать 2, так что подходят все 4 варианта закрытия.
depots=1, reach=1, roads=[] → 2
depots ≤ 10reach ≤ 10⁵roads) ≤ 1000roads[i] = [a, b, len], 0 ≤ a, b < depots, a ≠ bdepots=3, reach=4, roads=[[0, 1, 3], [1, 2, 3]]
6
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 86 тестов на сервере, включая скрытые.