BFS на 0-1 графе: почему обычная очередь даёт неверный кратчайший путь и при чём дек?

Обычный BFS даёт кратчайший путь, только если все рёбра равны: он обрабатывает вершины строго по слоям расстояния. Когда есть рёбра веса 0, вершина, достижимая по 0-ребру, должна иметь то же расстояние, что и текущая, а BFS-очередь поставит её «в следующий слой» — порядок обработки нарушается, и можно зафиксировать неоптимальное расстояние.

0-1 BFS чинит это деком: ребро веса 0 кладёт вершину в начало дека (тот же слой), ребро веса 1 — в конец (следующий слой). Так дек всегда содержит вершины не более чем двух соседних значений расстояния, и мы извлекаем их в правильном порядке.

vector<pair<int,int>> g[N];   // {сосед, вес 0 или 1}
vector<int> dist(n, INT_MAX);
deque<int> dq;
dist[s] = 0; dq.push_front(s);
while (!dq.empty()) {
    int v = dq.front(); dq.pop_front();
    for (auto [u, w] : g[v]) {
        if (dist[v] + w < dist[u]) {
            dist[u] = dist[v] + w;
            if (w == 0) dq.push_front(u);   // тот же слой — вперёд
            else        dq.push_back(u);    // следующий слой — назад
        }
    }
}

Сложность O(V+E) — линейно, как BFS, и без логарифма кучи (как у Дейкстры O(E log V)). Память O(V).

Грабля: вершина может попасть в дек несколько раз с разными расстояниями. При извлечении полезно проверять актуальность (if (dist[v] устарел) continue;) или просто полагаться на релаксацию — повторные обработки не нарушают корректность, но проверка экономит время.