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