- Считаем, что поезда ходят в обоих направлениях по каждому пути и в нулевой момент времени отправляются с обоих концов навстречу друг другу (иначе, возможно, на какие-то станции будет невозможно попасть).
- Пусть мы заходим на станцию в момент времени t0. Считаем время ожидания поезда для всех путей, которым принадлежит эта станция. Для этого для каждого пути найдем время t1 и t2, которое поезда, отправляющиеся с разных концов, тратят на то, чтобы добраться из начальной станции до текущей. Пусть T - периодичность, с которой на пути появляется новый поезд. Тогда время ожидания найдется либо как t_жд1 = t1 - t0, если t1 > t0, либо как t_жд1 = (t0 - t1) % T. Всем путям (ребрам) к соседним станциям присваиваем число t_ст = t_движения_до_станции + t_ожидания.
- Используем алгоритм Дейкстры для того, чтобы найти кратчайший по времени путь из станции отправления в станцию назначения. На каждой новой станции пересчитываем время на ребрах аналогично п. 1, только вместо t0 текущий момент времени. В конце работы алгоритма в вершине станции прибытия будет время оптимального маршрута.
Реализация. Карта = вектор из путей Путь = период появления новых поездов + вектор из начальной и конечной станций (там находятся все станции, имеющие на данный момент ввода входных данных одну станцию-соседа на данном пути) + map: (номер станции - пара из двух ее соседей на данном пути (сосед = пара: номер станции + время в пути до нее) (вторая компонента -1, если сосед 1))). Когда появляется новая станция, функция std::vector CountPaths(int StationNumber) ищет номера всех путей, которым она принадлежит. На каждом шаге перебираем все пути, выполняем подсчеты, как сказано в п. 1. t1 и t2 считаем, исходя из начальной и конечной станций пути.