УЧЕБНО - ТРЕНИРОВОЧНЫЕ СБОРЫ К IOI 2003 ДЕНЬ №5 Инкассаторы
Входной файл: input.txt Выходной файл: output.txt Время на тест: 2 секунды Ограничения на память: 16 MB Автор задачи: Сикорский А.О. Тесты к задаче:Скачать
Когда Макс Крейзи закончил финансовый колледж, он стал управляющим городского банка. Уже с первых дней работы Макс столкнулся с одной неразрешимой для него проблемой.
В стране, где живет Макс, есть N городов. Некоторые из них связанны двусторонними дорогами, которые пересекаются только в городах. Раз в месяц инкассаторы Макса должны доставить деньги в K сберкасс. Все K сберкасс находятся в различных городах. Пока банк Макса небогат и имеет всего одну машину для перевозки денег. Вам необходимо помочь Максу составить маршрут, который, начинается в городе L (в этом городе находится банк Макса), проходит по всем K городам, где находятся нужные сберкассы, и заканчивается также в городе L. Этот маршрут должен иметь минимальную длину (длиной маршрута назовем сумму длин всех дорог, входящих в этот маршрут).
Входные данные: InPut.txt
В первой строке через пробел три числа: N M K, где N - общее количество городов в стране, M - общее количество двусторонних дорог,K - количество сберкасс которые должны посетить инкассаторы(без учета города L).
Во второй строке через пробел идут K чисел - номера городов, где находятся сберкассы.
Следующие M строк содержат описание дорог. В каждой строке описывается одна дорога в виде X Y S, где X,Y - номера городов которые связаны дорогой и S - длина этой дороги.
В последней строке дано число L - номер города, где находится банк Макса.
Выходные данные: OutPut.txt
Единственная строка выходного файла должна содержать набор чисел - номеров городов искомого маршрута в порядке обхода. Эти числа должны быть разделены одиночными пробелами. В случае, когда такого маршрута не существует, выходной файл должен содержать одно слово "NO".
Ограничения.
1 < N <= 100
0 < M <= N(N-1)/2
0 < K < 18, K < N
0 < S <= 50000
1 <= L,X,Y <= N
Все входные данные - натуральные числа.