1. Идея

Нужно найти кратчайший путь из вершины 1 в вершину n, если:

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

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

Поэтому стандартный приём здесь — сделать двухслойный граф состояний:

• слой 0: турбо ещё не включали;
• слой 1: турбо уже включён.

Тогда состояние задаётся парой (вершина, режим).

После этого можно просто запустить алгоритм Дейкстры по этим состояниям.

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

Наблюдение 1. У каждой вершины есть два состояния

Для каждой вершины v возможны две ситуации:

• dist[0][v] — минимальная стоимость добраться до v, если турбо ещё не включали;
• dist[1][v] — минимальная стоимость добраться до v, если турбо уже включён.

Это и есть основа решения.

Наблюдение 2. Переходы между состояниями очень простые

Если мы находимся в состоянии (v, 0):

• можем пройти по ребру v -> to за цену w1, оставаясь в слое 0;
• можем в этой же вершине бесплатно включить турбо и перейти в состояние (v, 1).

Если мы находимся в состоянии (v, 1):

• можем пройти по ребру v -> to только за цену w2, оставаясь в слое 1.

Обратного перехода из слоя 1 в слой 0 нет.

Наблюдение 3. Все веса неотрицательны

w1 и w2 неотрицательны, переход между режимами тоже имеет стоимость 0.

Значит, на таком графе состояний корректно работает алгоритм Дейкстры.

Наблюдение 4. Ответ — минимум из двух состояний в вершине n

До конечной вершины можно:

• доехать, ни разу не включив турбо;
• доехать, уже включив турбо.

Поэтому ответ равен min(dist[0][n], dist[1][n]).

3. Алгоритм

Построим список рёбер исходного графа. Явно новый граф из 2n вершин строить не обязательно — достаточно просто хранить состояние mode в Дейкстре.

Шаги алгоритма

1. Считываем граф.
2. Создаём массив расстояний dist[2][n + 1], заполняем бесконечностью.
3. Стартовое состояние:
   • dist[0][1] = 0, потому что в вершине 1 ровер находится в обычном режиме.
4. Запускаем Дейкстру по состояниям (distance, vertex, mode).
5. Из состояния:
   • (v, 0):
     • можно перейти в (v, 1) с той же стоимостью;
     • по каждому ребру v -> to перейти в (to, 0) с добавлением w1;
   • (v, 1):
     • по каждому ребру v -> to перейти в (to, 1) с добавлением w2.
6. После завершения берём ans = min(dist[0][n], dist[1][n]).
7. Если ans остался бесконечностью, выводим -1, иначе выводим ans.

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

Докажем, что алгоритм действительно находит минимальную стоимость.

1. Любому допустимому маршруту соответствует путь в графе состояний

Рассмотрим любой маршрут ровера в исходной задаче.

В начале он находится в вершине 1 без включённого турбо, то есть в состоянии (1, 0).

Далее возможны два типа действий:

• пройти по ребру:
  • если турбо ещё не включали, добавляется w1;
  • если турбо уже включён, добавляется w2;
• один раз переключиться в турбо:
  • это переход (v, 0) -> (v, 1) с ценой 0.

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

2. Любому пути в графе состояний соответствует допустимый маршрут

Теперь наоборот: любой путь в графе состояний начинается в (1, 0) и использует только разрешённые переходы:

• движение по ребру в текущем режиме,
• либо однократный переход из слоя 0 в слой 1.

Такой путь точно описывает реальное движение ровера, потому что:

• из слоя 1 вернуться в слой 0 нельзя;
• переключение возможно только один раз.

Значит, любой путь в графе состояний соответствует допустимому маршруту в исходной задаче.

3. Задача свелась к обычшему кратчайшему пути

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

Алгоритм Дейкстры корректно находит минимальные расстояния до всех состояний.

Следовательно:

• dist[0][v] — действительно минимальная стоимость попасть в v, не включая турбо;
• dist[1][v] — действительно минимальная стоимость попасть в v, уже включив турбо.

Тогда минимальная стоимость достижения вершины n равна min(dist[0][n], dist[1][n]).

Это и есть правильный ответ.

5. Сложность

Пусть в графе n вершин и m рёбер.

Состояний всего 2n, потому что на каждую вершину есть два режима.

Из каждого состояния мы рассматриваем:

• либо все исходящие рёбра,
• плюс для слоя 0 ещё один переход переключения режима.

То есть число переходов порядка 2m + n, что асимптотически равно O(m + n).

Алгоритм Дейкстры работает за:

• O((n + m) log n)

Точнее, можно писать O((2n + 2m) log (2n)), но это то же самое по порядку.

По памяти:

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

Итого память: O(n + m).

6. Код на C++17

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

using namespace std;

struct Edge {
    int to;
    int w1;
    int w2;
};

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

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

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

    using State = tuple<long long, int, int>;
    priority_queue<State, vector<State>, greater<State>> pq;

    dist[0][1] = 0;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        auto [d, v, mode] = pq.top();
        pq.pop();

        if (d != dist[mode][v]) {
            continue;
        }

        if (mode == 0) {
            if (dist[1][v] > d) {
                dist[1][v] = d;
                pq.push({d, v, 1});
            }
        }

        for (const Edge& e : g[v]) {
            long long nd;
            if (mode == 0) {
                nd = d + e.w1;
                if (nd < dist[0][e.to]) {
                    dist[0][e.to] = nd;
                    pq.push({nd, e.to, 0});
                }
            } else {
                nd = d + e.w2;
                if (nd < dist[1][e.to]) {
                    dist[1][e.to] = nd;
                    pq.push({nd, e.to, 1});
                }
            }
        }
    }

    long long ans = min(dist[0][n], dist[1][n]);
    if (ans == INF) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\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, w1, w2 = map(int, input().split())
    g[u].append((v, w1, w2))

INF = 10**30
dist = [[INF] * (n + 1) for _ in range(2)]
dist[0][1] = 0

pq = [(0, 1, 0)]  # distance, vertex, mode

while pq:
    d, v, mode = heapq.heappop(pq)
    if d != dist[mode][v]:
        continue

    if mode == 0 and d < dist[1][v]:
        dist[1][v] = d
        heapq.heappush(pq, (d, v, 1))

    for to, w1, w2 in g[v]:
        if mode == 0:
            nd = d + w1
            if nd < dist[0][to]:
                dist[0][to] = nd
                heapq.heappush(pq, (nd, to, 0))
        else:
            nd = d + w2
            if nd < dist[1][to]:
                dist[1][to] = nd
                heapq.heappush(pq, (nd, to, 1))

ans = min(dist[0][n], dist[1][n])
if ans >= INF:
    print(-1)
else:
    print(ans)