Олег Виленович Деревенец - Песни о Паскале

чисел 47 P_47_1 Преобразование из десятичной системы P_47_2 Преобразование в десятичную систему 48 P_48_3 Логические операции с числами 49 P_49_1 Подсчет пересечений границ между странами P_49_2 Реклама «крестики-нолики» 50 P_50_1 Футбольный чемпионат, версия 2 P_50_2 Футбольный чемпионат, версия 3 51 P_51_1 Принцип действия указателей P_51_2 Действия с указателями, размеры указателей 53 P_53_1 Ввод и вывод массив указателей P_53_2 Сортировка массива указателей 54 P_54_1 Ввод и вывод списка P_54_2 Поиск в списке P_54_3 Сортированный список P_54_4 Поиск в сортированном списке 55 P_55_1 Частотный анализатор текста 56 P_56_1 Перестановка строк файла P_56_2 Запись в танцевальный кружок, версия 2 57 P_57_1 Ввод и вывод графа 58 P_58_1 Обход графа в ширину P_58_2 Поиск кратчайшего пути в графе 5959 P_59_1 Перестановка строк файла (используется модуль MyLibr) MyLibr Библиотечный модуль к программе P_59_1 61 P_61_1 Демонстрация работы Turbo Vision P_61_2 Программа с объектом типа «человек» P_61_3 Демонстрация наследования и полиморфизма

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

Представлена одна из задач 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

Библиография

1. Алексеев А. В. Олимпиады школьников по информатике. Задачи и решения. – Красноярск: Красноярское книжное издательство, 1995.

2. Андреева Е. В., Фалина И. Н. Информатика: Системы счисления и компьютерная арифметика. – М.: Лаборатория Базовых Знаний, 1999.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

4. Бабушкина И. А., Бушмелева Н. А., Окулов С. М., Черных С.Ю. Конспекты занятий по информатике (практикум по Паскалю). – Киров: Изд-во ВятГПУ, 1997.

5. Бадин Н. М., Волченков С. Г., Дашниц Н. Л., Корнилов П. А. Ярославские олимпиады по информатике. – Ярославль: Изд-во ЯрГУ, 1995.

6. Беров В. И., Лапунов А. В., Матюхин В. А., Пономарев А. А. Особенности национальных задач по информатике. – Киров: Триада-С, 2000.

7. Брудно А. Л., Каплан Л. И. Олимпиады по программированию для школьников / Под ред. Б. И. Наумова /. – М.: Наука, 1985. 96 с.

8. Брудно А. П., Каплан Л. И. Московские олимпиады по программированию. – М.: Наука, 1990.

9. Вирт Н. Алгоритмы+структуры данных=Программы. – М.: Наука, 1989.

10. Дагене В. А., Григас Г. К., Аугутис К. Ф. 100 задач по программированию. – М.: Просвещение, 1993.

11. Долинский М. С. Решение --">