1. Идея

Нужно найти кратчайший путь в ориентированном графе с неотрицательными весами рёбер от вершины s до вершины t.

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

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

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

1. Граф ориентированный, поэтому дорога u -> v не означает наличие дороги v -> u.

2. Все веса неотрицательны. Это ключевое условие для применения алгоритма Дейкстры.

3. Если мы уже нашли путь до вершины длины d, а потом встретили более длинный вариант, его можно игнорировать.

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

5. Так как сумма длин может быть большой, в C++ расстояния нужно хранить в типе long long.

3. Алгоритм

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

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

Алгоритм Дейкстры опирается на то, что все веса рёбер неотрицательны.

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

После этого мы пытаемся улучшить расстояния до соседей вершины v:

• если путь s -> ... -> v -> to оказался короче текущего dist[to], то обновляем его;
• иначе ничего делать не нужно.

Почему можно хранить в очереди несколько записей для одной вершины?
Потому что при каждом улучшении мы просто добавляем новую пару (новое расстояние, вершина). Старая запись остаётся, но позже будет отброшена проверкой cur_dist != dist[v].

В итоге:

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

Значит, ответом будет dist[t], либо -1, если добраться нельзя.

5. Сложность

Пусть n — число перекрёстков, m — число дорог.

• Построение графа: O(m)
• Алгоритм Дейкстры с кучей: O((n + m) log n)
  Обычно эту оценку записывают как O(m log n), так как m обычно не меньше n.

Память:

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

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

6. Код на C++17

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

using namespace std;

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> 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});
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, s});

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

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

        for (const auto& edge : graph[v]) {
            int to = edge.first;
            int w = edge.second;
            long long nd = cur_dist + 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())

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

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

pq = [(0, s)]

while pq:
    cur_dist, v = heapq.heappop(pq)

    if cur_dist != dist[v]:
        continue

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

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