1. Идея

Перед нами граф, но вес ребра здесь не фиксирован заранее: он зависит от того, в какой момент мы пришли в вершину.

Если мы находимся на острове u в момент времени cur, то для маршрута u -> v с параметрами d, p, t нужно понять:

• когда можно ближайший раз уехать;
• во сколько тогда окажемся на острове v.

После этого задачу можно решать алгоритмом Дейкстры:

• dist[x] — самое раннее время, когда можно попасть на остров x;
• из вершины с минимальным текущим временем пытаемся улучшить времена для всех исходящих маршрутов.

Главная особенность — правильно посчитать ближайшее отправление парома.

2. Наблюдения

У маршрута есть отправления в моменты:

• d
• d + p
• d + 2*p
• и так далее

Если мы пришли в момент cur, то возможны два случая.

Случай 1: пришли до первого отправления

Если cur <= d, то можно просто дождаться первого парома и уехать в момент d.

Случай 2: первое отправление уже прошло

Если cur > d, то нужно найти минимальный момент вида d + k*p, который не меньше cur.

То есть нужно найти минимальное целое k, для которого:

d + k*p >= cur

Отсюда:

k >= (cur - d) / p

Значит, нужен

k = ceil((cur - d) / p)

В целочисленной арифметике это считается так:

k = (cur - d + p - 1) / p

Тогда время отправления:

depart = d + k * p

А время прибытия:

arrive = depart + t

3. Алгоритм

1. Считываем n и m.
2. Строим список смежности: для каждого острова храним все исходящие маршруты.
3. Создаём массив dist, где:
   • dist[1] = 0,
   • остальные значения равны бесконечности.
4. Запускаем Дейкстру с приоритетной очередью, где элемент — пара:
   • текущее лучшее время прибытия,
   • номер острова.
5. Пока очередь не пуста:
   • достаём вершину u с минимальным временем curDist;
   • если это значение уже устарело, пропускаем;
   • для каждого маршрута u -> v:
     • вычисляем ближайшее возможное время отправления depart;
     • вычисляем arrive = depart + t;
     • если arrive < dist[v], обновляем dist[v] и кладём новое состояние в очередь.
6. После завершения:
   • если dist[n] не изменилось, выводим -1;
   • иначе выводим dist[n].

4. Почему это работает

Алгоритм Дейкстры работает, если при более раннем приходе в вершину нельзя оказаться в худшем положении, чем при более позднем. Здесь это условие выполняется.

Действительно, пусть на остров u можно попасть в два момента: time1 <= time2.

Тогда для любого маршрута из u:

• если прийти раньше, можно либо сесть на тот же паром, что и при позднем приходе,
• либо даже на более ранний.

Значит, функция "время прибытия в следующую вершину" не ухудшается при уменьшении времени прихода в текущую вершину. Это именно то свойство, которое позволяет применять Дейкстру к графу с зависимыми от времени рёбрами.

Почему после извлечения вершины из очереди её значение окончательное?

• В очереди всегда выбирается вершина с минимальным текущим временем.
• Любой другой путь к ней через ещё не обработанные вершины не может дать меньшее время, потому что все эти вершины достигаются не раньше.
• Значит, найденное значение уже минимально.

Для каждого ребра мы рассматриваем самый ранний возможный рейс после момента curDist. Если существует лучший путь в v через u, то он обязан использовать именно ближайшее доступное отправление, потому что более поздний рейс даст не меньшее время прибытия.

Следовательно, все релаксации корректны, а алгоритм находит минимальное возможное время прибытия на остров n.

5. Сложность

Пусть n — число островов, m — число маршрутов.

• Построение графа: O(m)
• Алгоритм Дейкстры: O((n + m) log n)

Итоговая сложность: O((n + m) log n)

Память:

• граф: O(m)
• массив расстояний и очередь: O(n + m)

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <limits>

using namespace std;

struct Edge {
    int to;
    long long d, p, t;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long d, p, t;
        cin >> u >> v >> d >> p >> t;
        g[u].push_back({v, d, p, t});
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        long long curDist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (curDist != dist[u]) {
            continue;
        }

        for (const Edge& e : g[u]) {
            long long depart;
            if (curDist <= e.d) {
                depart = e.d;
            } else {
                long long k = (curDist - e.d + e.p - 1) / e.p;
                depart = e.d + k * e.p;
            }

            long long arrive = depart + e.t;
            if (arrive < dist[e.to]) {
                dist[e.to] = arrive;
                pq.push({arrive, e.to});
            }
        }
    }

    if (dist[n] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dist[n] << '\n';
    }

    return 0;
}

7. Код на Python 3

import heapq

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v, d, p, t = map(int, input().split())
    g[u].append((v, d, p, t))

INF = 10**30
dist = [INF] * (n + 1)
dist[1] = 0

pq = [(0, 1)]

while pq:
    cur_dist, u = heapq.heappop(pq)
    if cur_dist != dist[u]:
        continue

    for v, d, p, t in g[u]:
        if cur_dist <= d:
            depart = d
        else:
            k = (cur_dist - d + p - 1) // p
            depart = d + k * p

        arrive = depart + t
        if arrive < dist[v]:
            dist[v] = arrive
            heapq.heappush(pq, (arrive, v))

if dist[n] == INF:
    print(-1)
else:
    print(dist[n])