sites узлов с номерами от 0 до sites - 1. Возможные кабели заданы в cables: cables[i] = [a, b, cost] — кабель между узлами a и b стоимостью cost. Если проложить все кабели, связаны окажутся все узлы.
*Самая дешёвая сеть* — набор кабелей, который связывает все узлы (из любого узла можно добраться до любого) и имеет наименьшую возможную суммарную стоимость. Таких сетей может быть несколько.
Разделите кабели на два вида:
- *обязательные* — входят в каждую самую дешёвую сеть (без такого кабеля самая дешёвая сеть подорожает или станет невозможной);
- *запасные* — входят в некоторые самые дешёвые сети, но не во все.
Верните [обязательные, запасные] — два списка индексов кабелей. Кабели, которые не входят ни в одну самую дешёвую сеть, не попадают никуда. Порядок индексов внутри списков любой.sites=4, cables=[[0, 1, 2], [1, 2, 3], [0, 2, 3], [2, 3, 1]] → [[3, 0], [1, 2]]
Самая дешёвая сеть стоит 6: кабели 0 и 3 плюс один из кабелей 1 или 2 (оба по 3). Кабели 0 и 3 нужны всегда, а 1 и 2 взаимозаменяемы.
sites=3, cables=[[0, 1, 5], [1, 2, 5], [0, 2, 9]] → [[0, 1], []]
Единственная самая дешёвая сеть — кабели 0 и 1 за 10. Кабель 2 не входит ни в одну дешёвую сеть.
sites=3, cables=[[0, 1, 4], [1, 2, 4], [0, 2, 4]] → [[], [0, 1, 2]]
sites=4, cables=[[0, 1, 2], [1, 2, 3], [0, 2, 3], [2, 3, 1]]
[[3, 0], [1, 2]]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 55 тестов на сервере, включая скрытые.