1. Идея

Нужно найти путь из s в t, у которого минимален не суммарный риск, а максимальный риск на одном участке пути.

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

Для такой задачи подходит модификация алгоритма Дейкстры.

Обычно в Дейкстре dist[v] — это минимальная сумма весов до вершины v. Здесь же будем хранить другой смысл:

• dist[v] — минимально возможное значение максимального риска на пути из s в v.

Тогда при переходе по ребру веса w из вершины v в вершину to новый риск пути будет равен:

• max(dist[v], w)

Потому что на новом пути самый опасный участок — это максимум из:

• самого опасного участка на пути до v,
• риска нового ребра.

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

Наблюдение 1

Если уже найден путь до вершины v с минимально возможным значением dist[v], то любой другой путь до v с большим значением неинтересен.

Это точно так же, как в обычной Дейкстре: худший вариант не поможет улучшить ответ.

Наблюдение 2

Операция перехода монотонна:

• если текущее значение cur увеличивается, то max(cur, w) тоже не уменьшится.

Именно благодаря этому алгоритм Дейкстры остаётся корректным.

Наблюдение 3

Если s == t, то ответ равен 0.

Действительно, можно никуда не идти, а на пустом пути нет ни одного участка, значит максимальный риск равен 0.

В эталонном решении это получается автоматически:

• dist[s] = 0,
• если s и t совпадают, ответ уже найден.

Наблюдение 4

Если вершина t недостижима из s, то её значение так и останется бесконечностью, и нужно вывести -1.

3. Алгоритм

Используем граф в виде списка смежности и приоритетную очередь.

Шаги

1. Считываем n, m, s, t.
2. Строим неориентированный граф:
   • для каждого ребра u v w добавляем
     • v в список u,
     • u в список v.
3. Создаём массив dist, изначально весь заполнен очень большим числом.
4. Присваиваем dist[s] = 0.
5. Кладём в приоритетную очередь пару (0, s).
6. Пока очередь не пуста:
   • достаём вершину v с минимальным текущим значением cur,
   • если это устаревшая запись, пропускаем,
   • если v == t, можно остановиться,
   • для каждого ребра v -> to веса w считаем:
     • nd = max(cur, w)
   • если nd < dist[to], обновляем dist[to] и добавляем новую пару в очередь.
7. После завершения:
   • если dist[t] не изменилось, выводим -1,
   • иначе выводим dist[t].

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

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

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

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

Когда мы идём из v в to по ребру веса w, новый путь имеет опасность:

• либо уже был опасный участок на пути до v,
• либо самым опасным становится новое ребро.

Поэтому значение для нового пути равно max(dist[v], w).

Это полностью соответствует условию задачи.

Почему можно использовать приоритетную очередь

Мы всегда достаём из очереди вершину с минимальным текущим значением dist.

Предположим, что мы достали вершину v со значением cur = dist[v]. Покажем, что это значение уже окончательное.

Если бы существовал лучший путь в v с меньшим значением, то по этому пути все промежуточные значения тоже не превышали бы этого меньшего значения. Значит, какая-то вершина на таком пути должна была бы быть обработана раньше и привести к улучшению dist[v] раньше, чем мы извлекли v с cur.

Противоречие.

Значит, когда вершина извлекается из очереди с актуальным значением, её dist уже минимально возможен.

Это тот же принцип, что и в обычной Дейкстре, только вместо суммы используется операция max.

Почему ранняя остановка корректна

Как только из очереди извлечена вершина t, её значение уже окончательное и минимально возможное. Поэтому можно сразу завершить алгоритм.

5. Сложность

Пусть n — число вершин, m — число рёбер.

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

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

• O((n + m) log n)

Память:

• список смежности O(n + 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;

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

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

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

    priority_queue<
        pair<long long, int>,
        vector<pair<long long, int>>,
        greater<pair<long long, int>>
    > pq;

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

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

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

        if (v == t) {
            break;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            long long w = edge.second;
            long long nd = max(cur, w);
            if (nd < dist[to]) {
                dist[to] = nd;
                pq.push({nd, to});
            }
        }
    }

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

    return 0;
}

7. Код на Python 3

import heapq

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

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

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

pq = [(0, s)]

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

    if v == t:
        break

    for to, w in g[v]:
        nd = max(cur, w)
        if nd < dist[to]:
            dist[to] = nd
            heapq.heappush(pq, (nd, to))

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