UniLecs #Task. Quick route
Задача: между некоторыми деревнями области ходят автобусы. Поскольку пассажиропоток здесь не очень большиой, то автобусы ходят всего несколько раз в день. Вам требуется добраться из деревни 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].
В данном случае в графе могут быть кратные ребра (несколько рейсом между двумя деревнями) и информацию о каждом рейсе необходимо хранить. Поэтому для каждой вершины будем хранить списки исходящих из нее ребер, то есть информацию о всех рейсах, выезжающих из этой деревни. Информация о рейсе включает в себя время отправления, деревню прибытия и время прибытия, то есть является кортежем из трех элементов.
Реализация
https://gist.github.com/unilecs/1f2c0fed3a7f209d0b8c4518d6e7469f
https://gist.github.com/unilecs/cc63a94b18d20848276bbcaddfbf5049
