Надёжный маршрут — разбор решения

1. Идея

У каждого канала есть надёжность p — вероятность его успешной работы.

Надёжность всего маршрута — это произведение надёжностей всех его каналов.

Значит, задача сводится к такой:

• есть граф;
• у каждого ребра есть число от 0 до 1 — вероятность успешного прохождения;
• нужно найти путь из s в t, у которого произведение этих чисел максимально.

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

Для такой задачи подходит алгоритм Дейкстры в изменённом виде:

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

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

Наблюдение 1. Что именно хранить в графе

В эталонном решении для каждого ребра хранится значение p — надёжность канала — и дальше используется переход:

cand = cur * p

По условию значение p задаётся напрямую во входных данных, поэтому его можно сразу записывать в граф без дополнительных вычислений.

Именно p участвует в произведении надёжности маршрута.

Наблюдение 2. Начальное значение

Если мы находимся в стартовой вершине s и ещё не прошли ни одного ребра, надёжность равна 1.

Поэтому:

• best[s] = 1.0
• для остальных вершин best[v] = 0.0

Наблюдение 3. Как работает жадность

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

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

Наблюдение 4. Недостижимость

Если из s в t пройти нельзя, значение best[t] так и останется 0.0. По условию в этом случае и нужно вывести 0.

3. Алгоритм

1. Считываем n, m, s, t.
2. Строим список смежности.
3. Для каждого канала считываем u, v, p — надёжность канала.
4. Добавляем ребро в обе стороны, так как граф двусторонний.
5. Создаём массив best, где best[v] — максимальная надёжность маршрута от s до v.
6. Инициализируем:
   • best[s] = 1.0
   • очередь с приоритетом, куда кладём пару (1.0, s).
7. Пока очередь не пуста:
   • достаём вершину v с максимальной текущей надёжностью cur;
   • если это устаревшая запись, пропускаем;
   • если v == t, можно завершить работу;
   • перебираем все рёбра v -> to с вероятностью p;
   • считаем cand = cur * p;
   • если cand > best[to], обновляем best[to] и кладём новое состояние в очередь.
8. Выводим best[t].

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

Докажем корректность идеи.

Пусть best[v] — лучшая надёжность, найденная для вершины v.

Когда мы извлекаем из очереди вершину v с максимальным значением cur, это значит, что среди всех ещё не обработанных вариантов путь до v сейчас самый надёжный.

Теперь важно понять, почему после этого значение для v уже окончательное.

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

• было cur,
• стало cur * p,
• где 0 <= p <= 1.

То есть никакой другой путь, который ещё не успел попасть в обработку и имеет меньшую текущую надёжность, не сможет потом превратиться в путь к v с большей надёжностью.

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

Переход

cand = cur * p

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

Если cand > best[to], значит найден более надёжный маршрут в вершину to, и его действительно нужно запомнить.

Если вершина t недостижима, никакое обновление для неё не произойдёт, поэтому best[t] останется равным 0, что и требуется вывести.

5. Сложность

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

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

С учётом ограничений это проходит.

Память:

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

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>

using namespace std;

struct Edge {
    int to;
    double p;
};

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

    vector<vector<Edge>> g(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        double p;
        cin >> u >> v >> p;
        g[u].push_back({v, p});
        g[v].push_back({u, p});
    }

    vector<double> best(n + 1, 0.0);
    priority_queue<pair<double, int>> pq;

    best[s] = 1.0;
    pq.push({1.0, s});

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

        if (cur < best[v]) {
            continue;
        }

        if (v == t) {
            break;
        }

        for (const Edge& e : g[v]) {
            double cand = cur * e.p;
            if (cand > best[e.to]) {
                best[e.to] = cand;
                pq.push({cand, e.to});
            }
        }
    }

    cout << fixed << setprecision(10) << best[t] << '\n';
    return 0;
}

7. Код на Python 3

import heapq

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

g = [[] for _ in range(n + 1)]

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

best = [0.0] * (n + 1)
best[s] = 1.0

pq = [(-1.0, s)]

while pq:
    neg_cur, v = heapq.heappop(pq)
    cur = -neg_cur

    if cur < best[v]:
        continue

    if v == t:
        break

    for to, p in g[v]:
        cand = cur * p
        if cand > best[to]:
            best[to] = cand
            heapq.heappush(pq, (-cand, to))

print("{:.10f}".format(best[t]))