Задача №113518. Города
Есть n городов в Байтландии, и k из них важные города, часто посещаемые королем. В стране есть m дорог, каждая из которых соединяет два города. К сожалению, состояние дорог настолько плохо, что король не может проехать через них с полной скоростью на своих спортивных автомобилях. Для каждой дороги известны затраты на ее обновление. Ваша задача - выбрать, какие дороги будут отремонтированы, чтобы все k важных города были связаны отремонтированными дорогами, а общая стоимость была как можно ниже.
Первая строка ввода содержит три целых числа n , k и m : количество городов, количество важных городов и количество дорог. Города пронумерованы 1, 2, ..., n . Вторая строка ввода содержит k целых чисел: важные города.
Следующие m строк, описывают дороги. Каждая строка содержит три целых числа a , b и c , что означает, что существует двунаправленная дорога между городами a и b , а стоимость ремонта дороги - c .
Гарантируется, что существует маршрут между любыми двумя городами.
Вы должны вывести минимальные затраты на ремонт дорог, чтобы король мог путешествовать между всеми важными городами на своих спортивных автомобилях.
Во всех тестах 1 ≤ c ≤ 10 9 и n ≥ k
Подгруппа 1 (22 баллов)
2 ≤ k ≤ 5
n ≤ 20
1 ≤ m ≤ 40
Подгруппа 2 (14 баллов)
2 ≤ k ≤ 3
n ≤ 10 5
1 ≤ m ≤ 2 * 10 5
Подгруппа 3 (15 баллов)
2 ≤ k ≤ 4
n ≤ 1000
1 ≤ m ≤ 2000
Подгруппа 4 (23 баллов)
k = 4
n ≤ 10 5
1 ≤ m ≤ 2 * 10 5
Подгруппа 5 (26 баллов)
k = 5
n ≤ 10 5
1 ≤ m ≤ 2 * 10 5
4 3 6 1 3 4 1 2 4 1 3 9 1 4 6 2 3 2 2 4 5 3 4 8
11