1. Идея

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

Так как все длины троп неотрицательны, для поиска кратчайших расстояний подходит алгоритм Дейкстры.

Чтобы потом восстановить маршрут, для каждой вершины будем хранить parent — из какой вершины мы пришли в неё по лучшему найденному пути. После завершения алгоритма можно пройти от t назад по массиву parent до s, а затем развернуть этот список.

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

1. Граф неориентированный, значит каждую тропу u v w нужно добавить в обе стороны:

   • из u в v,
   • из v в u.

2. Вес ребра может быть равен 0, но это не мешает алгоритму Дейкстры: важно только, что отрицательных весов нет.

3. Если dist[t] так и осталось бесконечностью, то пути из s в t не существует, и нужно вывести -1.

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

5. Для больших ограничений n до 100000 и m до 300000 нужен эффективный алгоритм. Полный перебор путей невозможен, а Дейкстра с очередью с приоритетом как раз подходит.

3. Алгоритм

1. Считываем n, m, s, t.
2. Строим список смежности g, где для каждой вершины хранятся пары (to, w).
3. Создаём:
   • массив dist, где dist[v] — минимальное найденное расстояние от s до v;
   • массив parent, где parent[v] — предыдущая вершина на кратчайшем пути;
   • приоритетную очередь, в которой лежат пары (расстояние, вершина).
4. Инициализация:
   • dist[s] = 0,
   • кладём (0, s) в очередь.
5. Пока очередь не пуста:
   • достаём вершину v с минимальным текущим расстоянием;
   • если это расстояние не совпадает с dist[v], значит запись устарела, её пропускаем;
   • перебираем все рёбра из v;
   • если через v можно улучшить расстояние до to, то:
     • обновляем dist[to],
     • записываем parent[to] = v,
     • добавляем новую пару в очередь.
6. После завершения:
   • если dist[t] бесконечно, выводим -1;
   • иначе восстанавливаем путь:
     • начинаем с t,
     • переходим по parent назад,
     • полученный список разворачиваем.
7. Выводим:
   • суммарную длину,
   • количество лагерей в маршруте,
   • сам маршрут.

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

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

Основная идея такая:

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

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

• когда мы улучшаем расстояние до вершины to через вершину v, мы запоминаем parent[to] = v;
• значит, у каждой вершины хранится предыдущая вершина на лучшем найденном пути;
• для вершины t последовательность t -> parent[t] -> parent[parent[t]] -> ... приводит назад к s;
• если развернуть эту последовательность, получится путь от s до t.

Почему путь действительно кратчайший:

• parent[to] меняется только тогда, когда найден путь короче предыдущего;
• в конце алгоритма dist[t] — это длина кратчайшего пути до t;
• цепочка parent соответствует именно тем переходам, которыми это расстояние было получено.

Почему проверка if cur_d != dist[v] важна:

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

5. Сложность

Пусть n — число лагерей, m — число троп.

• Построение графа: O(m).
• Алгоритм Дейкстры с приоритетной очередью: O((n + m) log n).
• Восстановление пути: O(k), где k — число вершин в маршруте, и k <= n.

Итоговая сложность: O((n + m) log n).

Память:

• список смежности: O(n + m),
• массивы dist и parent: O(n),
• очередь: до O(m) в худшем случае.

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

6. Код на C++17

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

using namespace std;

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

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

    const long long INF = (long long)4e18;
    vector<long long> dist(n + 1, INF);
    vector<int> parent(n + 1, -1);

    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_d = pq.top().first;
        int v = pq.top().second;
        pq.pop();

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

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

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

    vector<int> path;
    int cur = t;
    while (cur != -1) {
        path.push_back(cur);
        cur = parent[cur];
    }
    reverse(path.begin(), path.end());

    cout << dist[t] << '\n';
    cout << path.size() << '\n';
    for (int i = 0; i < (int)path.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << path[i];
    }
    cout << '\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)
parent = [-1] * (n + 1)

dist[s] = 0
pq = [(0, s)]

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

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

if dist[t] == INF:
    print(-1)
else:
    path = []
    cur = t
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()

    print(dist[t])
    print(len(path))
    print(*path)