house_count домов с номерами от 1 до house_count, и в каждый нужно провести воду. Есть два способа:
- выкопать колодец прямо в доме i — это стоит well_cost[i - 1];
- получить воду по трубе из соседнего дома, где вода уже есть. Запись pipes[j] = [a, b, cost] означает, что дома a и b можно соединить трубой за cost; вода по трубе течёт в обе стороны. Между одной парой домов может быть несколько вариантов трубы с разной ценой.
Верните наименьшую суммарную стоимость, при которой вода есть в каждом доме.house_count=3, well_cost=[5, 1, 4], pipes=[[1, 2, 2], [2, 3, 6]] → 7
Колодец в доме 2 за 1, труба 1–2 за 2. Для дома 3 свой колодец (4) дешевле трубы (6). Итого 1 + 2 + 4 = 7.
house_count=2, well_cost=[0, 0], pipes=[[1, 2, 3]] → 0
Колодцы бесплатные, трубы не нужны.
house_count=4, well_cost=[9, 9, 2, 9], pipes=[[1, 2, 1], [2, 3, 3], [3, 4, 1], [1, 4, 5]] → 7
house_count ≤ 10⁴well_cost) = house_countwell_cost[i] ≤ 10⁵pipes) ≤ 10⁴a, b ≤ house_count, a ≠ bcost ≤ 10⁵house_count=3, well_cost=[5, 1, 4], pipes=[[1, 2, 2], [2, 3, 6]]
7
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 76 тестов на сервере, включая скрытые.