В районе n пунктов выдачи Ozon, номера от 0 до n − 1. Поставить в пункт i свой роутер с тарифом стоит router[i] рублей в год. Кабель [u, v, c] между пунктами u и v стоит c рублей в год и работает в обе стороны.
Пункт с интернетом раздаёт его всем, с кем связан кабелями. Верните минимальную годовую стоимость, при которой интернет есть во всех пунктах.
В работе: Подключение нового кластера ПВЗ в спальном районе: где ставить роутеры, а где тянуть кабель через дорогу.
Пример 1
router = [9000, 2000, 7000] cables = [[0, 1, 1500], [1, 2, 6000]]
9500
Роутер в пункте 1 (2000), кабель 0–1 (1500), кабель 1–2 (6000) дешевле роутера в 2 (7000): итого 9500.
Пример 2
router = [300, 400] cables = []
700
Кабелей нет — роутер в каждом пункте.
Ограничения
- 1 ≤ n ≤ 10⁵
- 0 ≤ число кабелей ≤ 3·10⁵
- 1 ≤ router[i], c ≤ 10⁵
- Лимит — 3 с на тест (3000 мс).
print() и console.log() уходят в консоль.
def connect_pickup_points(router, cables):
Источник: наша задача на данных Ozon. Условие пересказано своими словами.
Ожидаемый ответ не нужен: покажем, что вернула функция.
Здесь появится результат отправки.