Чиновники і дороги#11146
У місті Фловіль відбулися вибори чиновників. Місто можна уявити як зв'язний неорієнтований граф, що складається з вершин і ребер. Кожне ребро графа описується трійкою чисел: u_i, v_i, len_i, де u_i і v_i — вершини, які з'єднує ребро, а len_i — його довжина.
Кожному чиновнику надається житло. Чиновнику з номером виділяється житло у вершині графа з номером h_t. У місті є офісів, де чиновники можуть працювати. Якщо чиновнику з номером виділено офіс у вершині графа з номером w_t, то він щодня їздитиме на автомобілі з вершини h_t до вершини w_t. Чиновник завжди обирає найкоротший шлях. Якщо існує кілька найкоротших шляхів, він обирає той, що є «лексикографічно найменшим» при упорядкуванні вершин маршруту у зворотному порядку (від офісу до дому).
Наприклад, якщо є два найкоротші шляхи з вершини 0 до вершини 5: 0→1→2→4→5 і 0→3→5, то чиновник обере шлях 0→3→5. У зворотному порядку ці шляхи виглядають як 5→4→2→1→0 і 5→3→0. Лексикографічно найменший — це 5→3→0.
Усі дороги (ребра графа), що входять до маршруту чиновника, завжди будуть підтримуватися в хорошому стані.
Кожному чиновнику потрібно вибрати лише один офіс з наявних, щоб сумарна довжина доріг, які будуть у хорошому стані, була максимальною.
У першому рядку через пробіл задано три цілі числа , та .
— кількість вершин графа (N \le 100);
— кількість ребер у графі (M \le 1000);
— кількість чиновників (T \le 8);
Далі йдуть рядків, що описують ребра графа. Кожне ребро задано у форматі: u_i v_i len_i, де len_i — довжина ребра (0 \le u_i, v_i \le n), (len_i \le 100000).
Далі йде рядок з цілих чисел:
0 \le h_1, h_2, …, h_t, …, h_T \le n — номери вершин, у яких знаходяться будинки чиновників;
Далі йде рядок з цілих чисел:
0 \le w_1, w_2, …, w_t, …, w_T \le n — номери вершин, у яких знаходяться офіси для майбутньої роботи чиновників.
— максимальна сумарна довжина доріг, які будуть гарантовано відремонтовані.
0 \le w_{res,1}, w_{res,2}, …, w_{res,t}, …, w_{res,T} \le n — номери вершин, у яких знаходяться офіси для майбутньої роботи чиновників, що відповідають максимальній сумарній довжині гарантовано відремонтованих доріг .
Приклад 1
Приклад 10
Приклад 11
Приклад 12