Чиновники и дороги
Чиновники и дороги
В городе Фловиль были проведены выборы T чиновников. Сам город можно представить в виде связного неориентированного графа, состоящего из N вершин и M рёбер. Каждое ребро графа задаётся тройкой чисел: u_iv_ilen_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.
Все дороги (рёбра графа) лежащие вдоль маршрута чиновника всегда будут будут поддерживаться в хорошем состоянии.
Каждому чиновнику необходимо выбрать только один офис из имеющихся в списке так, чтобы суммарная длина дорог, находящихся в хорошем состоянии, была максимальной.
Input data
В первой строке через пробел заданы три целых числа N, M и T.
N - количество вершин графа (N \le 100);
M - количество рёбер в графе (M \le 1000);
T - количество чиновников (T \le 8);
Далее идут M строк, описывающих рёбра графа. Каждое ребро задано в формате: u_iv_ilen_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 - номера вершин, в которых находятся офисы для будущей работы чиновников.
Output data
SUM - максимальная суммарная длина дорог, которые будут гарантированно отремонтированы.
0 \le w_res1, w_res2, …, w_rest, …, w_resT \le n - номера вершин, в которых находятся офисы для будущей работы чиновников, соответствующие максимальной суммарной длине гарантированно отремонтированных дорог SUM.
Examples
2 1 1 0 1 23153 0 1
23153 1
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
41027 1 3
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
27621 3 0
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
58582 1 2 0 5