| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 7 | 1 | 1 | 50.000% |
Рик и Морти обнаружили в другом измерении карту планеты, на которой изображены $n$ пунктов раскопок, соединенных тропинками. Тропинка с номером $i$ соединяет пункты с номерами $u_i$ и $v_i$ и имеет длину $c_i$.
Разумеется, Рик сразу заметил, что количество тропинок равняется в точности $n - 1,ドル и из любого пункта можно добраться до любого другого. Иными словами, структура дорог и пунктов представляет из себя дерево, но для Морти это определение слишком сложное, поэтому Рик оставил Морти изучать теорию графов, а сам отправился исследовать это измерение.
Инопланетный информатор сообщил ему, что всего существует $k$ видов артефактов, и в пункте номер $i$ хранится артефакт вида $a_i$. Так очень удачно совпало, что у Рика очередное соревнование с одним из известных расхитителей космических гробниц, и для победы Рику нужно собрать все $k$ различных видов артефактов.
Одной из проблем является то, что внутри этого измерения не работают никакие продвинутые технологии. Поэтому Рик может заранее создать порталы в запланированных стартовом и конечном пункте маршрута, а вот остальной маршрут придется пройти пешком. Чтобы сэкономить свое время, Рик хочет заранее выбрать стартовый пункт, конечный пункт и сам путь (не обязательно простой) так, чтобы пройденное им расстояние было минимальным, и при этом на пути он бы собрал все различные виды артефактов.
Рик, конечно, и сам может справиться с поиском такого кратчашего пути, но, может быть, у вас есть время заняться этим, пока он собирает всю необходимую для путешествия экипировку?
В первой строке через пробел даны два целых числа $n$ и $k$ (2ドル \leqslant n \leqslant 10^5$; 1ドル \leqslant k \leqslant 6$) --- количество пунктов и необходимое количество артефактов.
В следующей строке через пробел даны $n$ целых чисел $a_i$ --- виды артефактов в каждом пункте (0ドル \leqslant a_i \leqslant k$). В случае, если $a_i = 0,ドル считается, что в вершине не хранится никакой из видов артефактов.
В следующих $n - 1$ строках даны тройки целых чисел $u_i,ドル $v_i,ドル $c_i,ドル обозначающие наличие тропинки длины $c_i$ между пунктами $u_i$ и $v_i$ (1ドル \leqslant u_i, v_i \leqslant n$; 1ドル \leqslant c_i \leqslant 10^9$). Гарантируется, что структура графа представляет из себя дерево.
В случае, если невозможно собрать $k$ различных видов артефактов, выведите <<-1>> (без кавычек), иначе сообщите минимальное расстояние, которое придется пройти, чтобы собрать все виды артефактов.
5 4 1 3 2 4 4 1 3 1 2 3 1 3 4 1 4 5 1
4
5 5 1 3 2 4 4 1 3 1000 2 3 5123 3 4 3341 4 5 7197
-1
4 3 0 1 2 3 1 2 10 2 3 1 3 4 50
51
В первом примере одним из оптимальных путей будет 1ドル \to 3 \to 2 \to 3 \to 4$.
В втором примере у нас нет пункта, в котором находится артефакт под номером 5ドル,ドル а значит невозможно собрать все пять артефактов.
В третьем примере одним из оптимальных путей будет 2ドル \to 3 \to 4$.