Traffic jams (RU)
Traffic jams (RU)
В городе N
все дороги двусторонние. Система дорог города N
позволяет проехать из каждой точки города в любую другую, но из-за стремительного увеличения числа автомобилей постоянно возникают пробки, проехать через которые за разумное время практически невозможно. По настойчивой просьбе автомобилистов мэрия создала информационную службу, которая сообщает автомобилистам о том, как добраться из одной точки города в другую кратчайшим путем, то есть, проехав наименьшее возможное число перекрестков, минуя возникшие пробки. Напишите программу, которая позволит автоматически прокладывать этот кратчайший путь, облегчая жизнь как автомобилистам, так и сотрудникам службы.
Входные данные
В первой строке через пробел три целых числа: n
, m
, k
(3 <= n
, m <= 1000
, 1 <= k <= 50
); n
– количество перекрестков, m
– количество дорог, k
– количество запросов по расчету оптимального маршрута. Нумерация перекрестков, дорог и автомобилей начинается с единицы. Следующие m
строк задают список дорог в городе, в каждой строке пара чисел от 1 до n
через пробел – номера перекрестков, соединенных дорогой. Далее k
блоков, каждый из которых описывает один запрос. Блок начинается строкой, содержащей три целых числа, записанных через пробел: s
, f
, p
(1 <= s
, f
, p <= m
), s
, f
– номера дорог, являющихся начальным и целевым пунктом движения автомобиля соответственно, p
– количество пробок. В следующих p
строках по одному числу от 1 до m
- номера дорог, на которых возникли пробки.
Выходные данные
Выходной файл содержит k
блоков, описывающих маршрут движения автомобиля с минимальным количеством пройденных перекрестков. В первой строке блока выводится целое число – количество перекрестков, через которые проходит маршрут. Во второй строке маршрут - последовательность номеров перекрестков (целых чисел от 1 до n
) через пробел. Гарантируется, что маршрут из начального пункта в конечный всегда существует.
7 8 2 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 5 7 4 1 8 1 5 1 2
3 7 6 5 2 1 5