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