Песни о Паскале

Приложение М Пример олимпиадной задачи

Представлена одна из задач XVII районной (городской) олимпиады по информатике Московской области 2004 г.

Трамвайная сеть города состоит из N трамвайных остановок, пронумерованных числами от 1 до N. Остановки соединяются друг с другом M перегонами, пронумерованными числами от 1 до M. На трамвайных остановках есть стрелки для перехода трамвая с любого ведущего к остановке перегона на любой другой перегон, ведущий от нее. Все перегоны имеют одинаковую длину, но принадлежат к двум типам: односторонние и двухсторонние. По односторонним перегонам трамваи могут двигаться только в одном направлении; по двусторонним – в обоих, но вдвое медленнее, чем по односторонним.

По заданной схеме трамвайной сети города найти кратчайший по времени путь между двумя заданными остановками, при условии, что трамваи никогда не мешают друг другу (в городе один трамвай). Входные данные гарантируют, что путь между остановками всегда существует.

В первой строке входного файла приведено количество остановочных пунктов N (2≤ N≤ 100) и число перегонов M (1 ≤ M ≤ 30000). Далее идут M строк с описаниями перегонов по одному описанию в строке. Каждое описание состоит из четырех чисел, разделенных пробелом: номера перегона; двух номеров остановок, которые соединяет данный перегон; тип перегона (1 – если перегон односторонний и 2 – если двусторонний). Если перегон односторонний, то движение трамваев по нему разрешается от первого остановочного пункта в описании ко второму. Далее следует строка с двумя номерами остановок, между которыми следует найти кратчайший по времени путь (от исходной остановки к конечной)

В выходной файл «output.txt» следует вывести список номеров остановочных пунктов и перегонов между ними в порядке их прохождения трамваем. В случае нескольких возможных правильных ответов вывести любой из них.

Входные данные

4 61 2 1 12 2 1 23 1 3 15 2 4 24 2 3 26 4 3 11 4

Вывод

1 2 2 5 4