| Algo Cup 2025 by csspace.io (Финал) |
|---|
| Закончено |
Вам дан неориентированный взвешенный граф, состоящий из $$$n$$$ вершин и $$$m$$$ рёбер. Вершины графа пронумерованы целыми числами от $$$1$$$ до $$$n$$$. В вершине $$$i$$$ записано целое число $$$a_i$$$, а у каждого ребра графа есть стоимость.
Путь — это последовательность попарно-различных вершин, где любые две последовательные вершины соединены ребром. Стоимость пути определяется как сумма стоимостей всех рёбер на этом пути.
Определим красоту пути, состоящего из вершин $$$v_1, v_2, \dots, v_c$$$, как сумму $$$a_{v_1} + a_{v_2} + \cdots + a_{v_c}$$$ чисел, записанных в его вершинах. Назовём путь красивым, если его красота делится на $$$k$$$ без остатка.
Ваша задача — найти красивый путь с наименьшей возможной стоимостью или сообщить, что красивых путей не существует.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 10\,000$$$; $$$1\le m \le 10\,000$$$; $$$2 \le k \le 6$$$) — количество вершин в графе, количество рёбер в графе и необходимый делитель красоты пути соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \lt a_i \lt k$$$) — числа, записанные в вершинах.
Затем следуют $$$m$$$ строк, $$$i$$$-я из них содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 10^9$$$), означающих, что $$$i$$$-е ребро графа соединяет вершины $$$x_i$$$ и $$$y_i$$$ и имеет стоимость $$$w_i$$$.
Гарантируется, что заданный граф не содержит петель или кратных рёбер.
В единственной строке выведите единственное целое число — минимально возможную стоимость красивого пути, или -1, если красивых путей в заданном графе не существует.
4 4 31 1 2 11 2 12 3 44 3 54 1 1
2
2 1 42 31 2 1
-1
| Название |
|---|


