1. Идея

Нужно найти минимальную стоимость пути в ориентированном графе, где вес каждого ребра равен только 0 или 1.

Обычный BFS подходит только для графов, где все рёбра имеют одинаковый вес. Алгоритм Дейкстры здесь тоже работает, но можно сделать проще и быстрее с помощью специального приёма — 0-1 BFS.

Главная идея такая:

• если идём по ребру веса 0, новая вершина должна рассматриваться как можно раньше;
• если идём по ребру веса 1, новая вершина может подождать немного дольше.

Поэтому вместо обычной очереди используем deque:

• вершину, достигнутую по ребру 0, кладём в начало;
• вершину, достигнутую по ребру 1, кладём в конец.

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

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

Наблюдение 1. Весов всего два типа

Все тоннели имеют стоимость только 0 или 1. Это очень важное ограничение: именно оно позволяет заменить приоритетную очередь на двустороннюю очередь.

Наблюдение 2. Если нашли более дешёвый путь, расстояние нужно обновить

Пусть сейчас мы стоим в зале v, и у нас уже известно минимальное на данный момент расстояние dist[v]. Тогда для каждого тоннеля v -> to со стоимостью w можно попробовать улучшить значение dist[to]:

dist[to] > dist[v] + w

Если это так, то найден лучший путь в to, и его надо запомнить.

Наблюдение 3. Почему appendleft для нулевого ребра

Если ребро бесплатное, то расстояние до новой вершины не увеличивается. Значит, такую вершину логично обработать раньше тех, у кого расстояние стало больше на 1.

Поэтому:

• w == 0 → добавляем в начало deque;
• w == 1 → добавляем в конец deque.

Наблюдение 4. Петли и кратные рёбра не мешают

В условии разрешены:

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

Алгоритм спокойно работает и в этом случае: он просто проверяет, даёт ли очередное ребро улучшение расстояния.

3. Алгоритм

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

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

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

Какой порядок обработки нужен

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

Здесь расстояние может увеличиться только:

• на 0,
• или на 1.

Если из вершины с расстоянием d мы идём:

• по бесплатному тоннелю, то получаем вершину тоже с расстоянием d;
• по платному тоннелю, то получаем вершину с расстоянием d + 1.

Значит, среди всех вершин, которые появляются после обработки текущей, сначала нужно разбирать вершины с расстоянием d, а потом уже с расстоянием d + 1.

Именно это и делает deque:

• нулевые рёбра отправляют вершину в начало;
• единичные — в конец.

Почему улучшения не теряются

Каждый раз, когда мы находим более короткий путь в вершину to, мы обновляем dist[to] и снова помещаем её в deque. Это означает, что если раньше вершина была достигнута не самым выгодным способом, позже она всё равно будет переобработана с лучшим расстоянием.

Почему ответ минимальный

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

Так как:

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

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

Следовательно, dist[t] — это минимальная суммарная стоимость пути из s в t. Если добраться нельзя, значение не изменится, и тогда нужно вывести -1.

5. Сложность

Пусть n — число залов, m — число тоннелей.

• Построение графа: O(m)
• Работа 0-1 BFS: O(n + m)

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

Память:

• граф хранит все рёбра: O(n + m)
• массив расстояний: O(n)
• очередь deque: O(n) в типичной оценке

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <deque>

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});
    }

    const int INF = 1000000000;
    vector<int> dist(n + 1, INF);
    deque<int> dq;

    dist[s] = 0;
    dq.push_back(s);

    while (!dq.empty()) {
        int v = dq.front();
        dq.pop_front();

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                if (w == 0) {
                    dq.push_front(to);
                } else {
                    dq.push_back(to);
                }
            }
        }
    }

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

    return 0;
}

7. Код на Python 3

from collections import deque

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))

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

dq = deque([s])

while dq:
    v = dq.popleft()
    for to, w in g[v]:
        nd = dist[v] + w
        if nd < dist[to]:
            dist[to] = nd
            if w == 0:
                dq.appendleft(to)
            else:
                dq.append(to)

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