Задачи
Чиновники и дороги
Чиновники и дороги
В городе Фловиль были проведены выборы $T$ чиновников. Сам город можно представить в виде связного неориентированного графа, состоящего из $N$ вершин и $M$ рёбер. Каждое ребро графа задаётся тройкой чисел: $u_i$ $v_i$ $len_i$ (ребро между вершинами $u_i$ и $v_i$) $len_i$ - длина ребра.
Каждому чиновнику предоставляется жильё. Чиновнику с номером $t$ предоставляется жильё в вершине графа с номером $h_t$. В городе имеется $T$ свободных офисов для работы чиновников. Если чиновнику с номером $t$ предоставлен офис в вершине графа с номером $w_t$, то ежедневно чиновнику необходимо ехать на автомобиле из вершины $h_t$ в вершину $w_t$. Чиновник обязательно будет ехать по кратчайшему пути. Из всех возможных кратчайших путей он выбирает маршрут по следующему правилу: упорядочим номера вершин маршрута в обратном порядке (т.е. от места работы к дому) и выберем «лексикографически наименьший» путь.
Например, если существуют 2 кратчайших пути из вершины 0 в вершину 5: 0→1→2→4→5 и 0→3→5, то чиновник выберет путь 0→3→5. Т.к. в обратном порядке (от места работы к дому): 5→4→2→1→0 и 5→3→0. А «лексикографически наименьший» - это 5→3→0.
Все дороги (рёбра графа) лежащие вдоль маршрута чиновника всегда будут поддерживаться в хорошем состоянии.
Каждому чиновнику необходимо выбрать только один офис из имеющихся в списке так, чтобы суммарная длина дорог, находящихся в хорошем состоянии, была максимальной.
\InputFile
В первой строке через пробел заданы три целых числа $N$, $M$ и $T$.
$N$ - количество вершин графа ($N \le 100$);
$M$ - количество рёбер в графе ($M \le 1000$);
$T$ - количество чиновников ($T \le 8$);
Далее идут $M$ строк, описывающих рёбра графа. Каждое ребро задано в формате: $u_i$ $v_i$ $len_i$, где $len_i$ - длина ребра ($0 \le u_i, v_i \le n$), ($len_i \le 100000$).
Далее идёт строка из $T$ целых чисел:
$0 \le h_1, h_2, …, h_t, …, h_T \le n$ - номера вершин, в которых находятся дома чиновников;
Далее идёт строка из T целых чисел:
$0 \le w_1, w_2, …, w_t, …, w_T \le n$ - номера вершин, в которых находятся офисы для будущей работы чиновников.
\OutputFile
$S$ - максимальная суммарная длина дорог, которые будут гарантированно отремонтированы.
$0 \le w_{res,1}, w_{res,2}, …, w_{res,t}, …, w_{res,T} \le n$ - номера вершин, в которых находятся офисы для будущей работы чиновников, соответствующие максимальной суммарной длине гарантированно отремонтированных дорог $S$.
Входные данные #1
2 1 1 0 1 23153 0 1
Выходные данные #1
23153 1
Входные данные #10
4 6 2 0 1 29108 1 2 9431 2 3 13527 1 3 11700 0 3 15800 0 2 32762 0 2 1 3
Выходные данные #10
41027 1 3
Входные данные #11
4 6 2 0 2 28448 1 2 20356 2 3 20979 1 3 11573 0 3 5345 0 1 1920 1 2 0 3
Выходные данные #11
27621 3 0
Входные данные #12
8 28 4 0 6 18908 1 2 10301 2 6 16463 3 7 17955 4 6 24411 5 7 20593 6 7 14513 4 5 8815 1 5 27654 2 5 20498 5 6 2903 0 2 5948 0 3 10273 1 6 27176 0 4 20959 0 7 27279 3 5 20876 0 1 10508 0 5 30777 4 7 9098 2 4 9328 2 3 15458 2 7 5043 3 4 12659 1 4 271 1 7 32408 3 6 17316 1 3 28695 3 4 6 7 0 1 2 5
Выходные данные #12
58582 1 2 0 5