|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 06-4. Автобусы
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
Марие Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
Формат входных данных
Во входном файле записано число N - общее число деревень (1 <= N <= 100),
номера деревень d и v, затем количество автобусных рейсов R (0 <= R <= 10000).
Затем идут описания автобусных рейсов. Каждый рейс задается номером
деревни отправления, временем отправления, деревней назначения
и временем прибытия (все времена - целые от 0 до 10000). Если
в момент t пассажир приезжает в какую-то деревню, то уехать из
нее он может в любой момент времени, начиная с t.
Формат выходных данных
В выходной файл вывести минимальное время, когда Мария Ивановна может
оказаться в деревне v. Если он не сможет с помощью указанных автобусных
рейсов добраться из d в v, вывести -1.
Пример
| input.txt | output.txt |
3 1 3 4 1 0 2 5 1 1 2 3 2 3 3 5 1 1 3 10 |
5 |