Фермер Джон переезжает. Он хочет найти лучшее место для новой фермы, так чтобы минимизировать расстояние, которое он будет покрывать каждый день.
Регион, в который ФД планирует переехать, имеет N городов (1 <= N <= 10,000). Там имеется M двунаправленных дорог (1 <= M <= 50,000), соединяющих определенные пары городов. Все города достижимы друг для друга через некоторую комбинацию дорог. Требуется выбрать город, в котором поселится ФД.
В K (1 <= K <= 5) из этих городов имеется рынки, которые ФД планирует посещать каждый день. А именно, каждый день ФД планирует выехать со своей новой фермы, посетить все K городов с рынками и вернутся домой. ФД может посещать рынки в произвольном порядке. Город для совей новой фермы он обязательно должен выбрать в одном Из N-K городов, которые не имеют рынка (цена проживания там существенно ниже).
Пожалуйста, помогите ФД вычислить минимальное расстояние, которое он будет ежедневное проезжать, если он выберет наилучший город и наилучший маршрут.
PROBLEM NAME: relocate
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа, N, M, K.
* Строки 2..1+K: Строка i+1 содержит целое число в диапазоне 1...N Указывающее город, содержащий i-ый рынок. Все рынки находятся в различных городах.
* Строки 2+K..1+K+M: Каждая строка содержит 3 разделенных одиночными пробелами целых числа, i, j (1 <= i,j <= N), L (1 <= L <= 1000), указывающих наличие дороги длиной L между городами I и J.
Формат выходных данных
* Строка 1: Минимальное расстояние, которое ФД будет проезжать каждый день, если он выберет город для проживания оптимально и спланирует маршрут движения оптимально.
Примечание
ФД построит ферму в городе 5. Его ежедневный маршрут будет таким: 5-1-2-3-2-1-5, общий путь равен 12.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 10
|
12
|