Остановка в столице — разбор задачи

1. Идея

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

Такой маршрут естественно разбивается на две части:

• путь из s в v;
• путь из v в t.

Тогда ответ равен:

• dist(s, v) + dist(v, t), если обе части существуют;
• -1, если хотя бы одна из них недостижима.

Так как граф неориентированный, расстояние от s до v равно расстоянию от v до s. Поэтому удобно один раз запустить алгоритм Дейкстры из вершины v и получить расстояния до всех аэропортов сразу.

После этого:

• dist[s] — это стоимость кратчайшего пути между v и s;
• dist[t] — это стоимость кратчайшего пути между v и t.

Ответ будет равен dist[s] + dist[t].

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

Наблюдение 1

Маршрут обязан проходить через v, значит любой допустимый путь имеет вид:

... -> v -> ...

То есть его можно разбить ровно в точке v.

Наблюдение 2

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

Наблюдение 3

Не нужно отдельно искать путь из s в v и из v в t двумя запусками.

Достаточно одного запуска из v, потому что в неориентированном графе:

• расстояние от v до s такое же, как от s до v;
• расстояние от v до t такое же, как от t до v.

Наблюдение 4

Если v = s, то первая часть маршрута имеет стоимость 0. Если v = t, то вторая часть маршрута имеет стоимость 0. Алгоритм это обрабатывает автоматически.

3. Алгоритм

1. Считываем n, m, s, v, t.
2. Строим список смежности неориентированного графа.
3. Запускаем алгоритм Дейкстры из вершины v.
4. Получаем массив dist, где dist[x] — минимальная стоимость пути из v в x.
5. Если dist[s] или dist[t] бесконечны, выводим -1.
6. Иначе выводим dist[s] + dist[t].

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

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

Пусть существует некоторый допустимый маршрут из s в t, проходящий через v. Тогда его можно представить как объединение двух маршрутов:

• из s в v;
• из v в t.

Стоимость всего маршрута равна сумме стоимостей этих двух частей.

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

То же самое верно и для второй части, от v до t.

Значит минимальная стоимость допустимого маршрута равна:

кратчайший путь от s до v + кратчайший путь от v до t.

Так как граф неориентированный, это то же самое, что:

кратчайший путь от v до s + кратчайший путь от v до t.

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

Если хотя бы одна из вершин s или t недостижима из v, то не существует маршрута s -> v -> t, и нужно вывести -1.

Следовательно, алгоритм всегда выводит правильный ответ.

5. Сложность

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

• Построение графа: O(m)
• Один запуск Дейкстры: O((n + m) log n)

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

O((n + m) log n)

Память:

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

Итого по памяти:

O(n + m)

6. Код на C++17

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

using namespace std;

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

    vector<vector<pair<int, int>>> graph(n + 1);

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

    const long long INF = numeric_limits<long long>::max() / 4;
    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[v_need] = 0;
    pq.push({0, v_need});

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

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

        for (auto edge : graph[u]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[to] > dist[u] + w) {
                dist[to] = dist[u] + w;
                pq.push({dist[to], to});
            }
        }
    }

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

    return 0;
}

7. Код на Python 3

import heapq

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

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

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

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

pq = [(0, v_need)]

while pq:
    cur_d, u = heapq.heappop(pq)

    if cur_d != dist[u]:
        continue

    for to, w in graph[u]:
        nd = cur_d + w
        if nd < dist[to]:
            dist[to] = nd
            heapq.heappush(pq, (nd, to))

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