Описание задачи
Найти самое быстрое соединение из станции A в станцию C с обязательной пересадкой в B. Прямых рейсов A→C нет.
Формат расписания
> Timetable:
станция время_отпр время_приб компания
- Если станция
A— поезд едет A→B - Если станция
B— поезд едет B→C
Запрос
? время_старта_из_A
Логика поиска
- Найти рейс из A с отправлением ≥ запрошенного времени
- Найти рейс из B с отправлением ≥ времени прибытия первого поезда
- Минимизировать время прибытия в C
Формат выходных данных
станция отпр приб компания
станция отпр приб компания
Или Connection does not exist. если нет подходящего маршрута.
Примеры
Расписание
> Timetable:
A 08:00:00 09:30:00 RegioJet
B 19:30:00 21:00:00 Ceske_drahy
A 06:45:00 08:15:00 Arriva
B 17:15:00 18:45:00 RegioJet
Query: ? 1:1:1
A 06:45:00 08:15:00 Arriva
B 17:15:00 18:45:00 RegioJet
Стартуем ≥ 01:01:01. Первый поезд из A: 06:45, прибываем в B в 08:15. Первый поезд из B после 08:15: 17:15. Прибываем в C в 18:45.
Query: ? 12:12:12
Connection does not exist.
Нет поездов из A после 12:12:12 или нет пересадки в B.
Ключевые моменты
- Время в формате HH:MM:SS
- Сортировать рейсы по времени отправления
- Бинарный поиск для эффективности
- Учесть, что пересадка требует времени: приб_A→B ≤ отпр_B→C