Разбор задачи «Путь с пересадками»

1. Идея

Нужно найти минимальную стоимость пути из s в t, если можно использовать не более k + 1 рейса.

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

Главная идея: хранить динамику по числу использованных рейсов.

Обозначим dist[i][v] — минимальная стоимость оказаться в аэропорту v, использовав не более i рейсов.

Тогда ответом будет минимальное значение среди dist[0][t], dist[1][t], ..., dist[k + 1][t].

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

Наблюдение 1

Если разрешено не более k пересадок, это значит, что можно использовать не более k + 1 рейса.

Например:

• k = 0 — только прямой рейс;
• k = 1 — можно лететь двумя рейсами;
• k = 2 — можно лететь тремя рейсами.

Наблюдение 2

Если мы знаем все лучшие стоимости для маршрутов с не более чем used рейсами, то можем получить значения для used + 1 рейсов двумя способами:

• вообще никуда не лететь дальше, то есть просто сохранить уже найденное значение;
• пройти по любому ребру u -> v стоимости w и попробовать перейти: dist[used + 1][v] = min(dist[used + 1][v], dist[used][u] + w).

Наблюдение 3

Все веса неотрицательные, но это решение вообще не опирается на Дейкстру. По сути это ограниченный по количеству шагов вариант релаксации рёбер, похожий на идею Беллмана–Форда.

Наблюдение 4

Ограничение k <= 100 очень маленькое по сравнению с n и m. Поэтому можно сделать k + 1 проход по всем рёбрам.

3. Алгоритм

1. Считываем все рёбра в список.
2. Создаём таблицу dist размера (k + 2) x (n + 1).
   • dist[i][v] — минимальная стоимость попасть в v, использовав не более i рейсов.
3. Заполняем всё бесконечностью.
4. Стартовое состояние:
   • dist[0][s] = 0.
5. Для каждого used от 0 до k:
   • сначала переносим все уже найденные значения:
     • для каждой вершины v делаем dist[used + 1][v] = min(dist[used + 1][v], dist[used][v]);
   • затем пробуем пройти по каждому ребру u -> v с ценой w:
     • если dist[used][u] достижимо, то улучшаем dist[used + 1][v].
6. После этого берём минимум среди всех dist[i][t], где 0 <= i <= k + 1.
7. Если минимум остался бесконечностью, выводим -1, иначе выводим найденную стоимость.

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

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

Что хранит dist[i][v]

После завершения вычислений для строки i значение dist[i][v] равно минимальной стоимости добраться из s в v, используя не более i рейсов.

Покажем это по индукции.

База

Для i = 0:

• dist[0][s] = 0, потому что в стартовой вершине можно находиться без единого рейса;
• для всех остальных вершин dist[0][v] = INF, потому что без рейсов туда попасть нельзя.

Значит, база верна.

Переход

Предположим, что для некоторого used значения dist[used][v] уже корректны.

Рассмотрим, как строится dist[used + 1].

Есть два типа допустимых маршрутов в вершину v с не более чем used + 1 рейсами:

1. Маршрут использует не более used рейсов.
   Тогда его стоимость уже учтена в dist[used][v], и мы переносим это значение в dist[used + 1][v].

2. Маршрут использует ровно на один рейс больше.
   Тогда его последний рейс имеет вид u -> v, а до u мы добрались не более чем за used рейсов. По предположению индукции лучшая такая стоимость равна dist[used][u], значит общая стоимость равна dist[used][u] + w. Все такие варианты мы перебираем проходом по рёбрам.

Мы рассмотрели все возможные маршруты длины не более used + 1 рейсов, значит dist[used + 1][v] вычисляется правильно.

Итог

После всех итераций мы корректно знаем минимальные стоимости для всех количеств рейсов от 0 до k + 1. Поэтому минимум по dist[i][t] и есть ответ задачи.

5. Сложность

Пусть:

• n — число аэропортов,
• m — число рейсов.

Тогда:

• по вершинам делается k + 1 проход,
• по рёбрам тоже k + 1 проход.

Итоговая сложность:

• время: O((k + 1) * (n + m)),
• память: O((k + 2) * n).

С учётом k <= 100 такое решение проходит по ограничениям.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v;
    long long w;
};

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    int k;
    cin >> k;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    const long long INF = (long long)4e18;
    vector<vector<long long>> dist(k + 2, vector<long long>(n + 1, INF));
    dist[0][s] = 0;

    for (int used = 0; used <= k; used++) {
        for (int j = 1; j <= n; j++) {
            dist[used + 1][j] = min(dist[used + 1][j], dist[used][j]);
        }
        for (const Edge& e : edges) {
            if (dist[used][e.u] != INF) {
                long long cand = dist[used][e.u] + e.w;
                if (cand < dist[used + 1][e.v]) {
                    dist[used + 1][e.v] = cand;
                }
            }
        }
    }

    long long ans = INF;
    for (int used = 0; used <= k + 1; used++) {
        ans = min(ans, dist[used][t]);
    }

    if (ans == INF) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

7. Код на Python 3

n, m, s, t = map(int, input().split())
k = int(input())

edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

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

for used in range(k + 1):
    for v in range(1, n + 1):
        if dist[used][v] < dist[used + 1][v]:
            dist[used + 1][v] = dist[used][v]
    for u, v, w in edges:
        if dist[used][u] != INF:
            cand = dist[used][u] + w
            if cand < dist[used + 1][v]:
                dist[used + 1][v] = cand

ans = min(dist[used][t] for used in range(k + 2))
if ans == INF:
    print(-1)
else:
    print(ans)