Анонс #230. Быстрый маршрут

Анонс #230. Быстрый маршрут

UniLecs

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

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

1. N – общее число деревень (1⩽N⩽100)

2. d и v - номера деревень

3. R - количество автобусных рейсов (0⩽R⩽10000). 

4. Описание автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000). 

Примечание: если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.

Вывод: Выведите минимальное время, когда вы сможете оказаться в деревне v. Если это невозможно, выведите -1.

Пример: 

1. N = 3

2. d = 1; v = 3

3. R = 4

[ { 1 0 2 5 },

{ 1 1 2 3 },

{ 2 3 3 5 },

{ 1 1 3 10 } ]

Output: 5.

Report Page