UniLecs #Task. Quick route

Albert Davletov
UniLecs
Published in
2 min readJul 20, 2020

Задача: между некоторыми деревнями области ходят автобусы. Поскольку пассажиропоток здесь не очень большиой, то автобусы ходят всего несколько раз в день. Вам требуется добраться из деревни 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.

Разбор

Задачу можно решить алгоритмом Дейкстры, но его необходимо модифицировать. Вместо расстояния до вершины i будем хранить Time[i] — минимальное время, за которое можно добраться до деревни i.

Рассмотрим процедуру релаксации ребра. Пусть из деревни start есть автобус в деревню finish, время отправления start_time, время прибытия — finish_time. Тогда при помощи этого автобуса можно улучшить значение Time[finish], если start_time >= Time[start] и finish_time < Time[finish].

В данном случае в графе могут быть кратные ребра (несколько рейсом между двумя деревнями) и информацию о каждом рейсе необходимо хранить. Поэтому для каждой вершины будем хранить списки исходящих из нее ребер, то есть информацию о всех рейсах, выезжающих из этой деревни. Информация о рейсе включает в себя время отправления, деревню прибытия и время прибытия, то есть является кортежем из трех элементов.

Реализация

C++

https://gist.github.com/unilecs/1f2c0fed3a7f209d0b8c4518d6e7469f

Python

https://gist.github.com/unilecs/cc63a94b18d20848276bbcaddfbf5049

--

--