Графы для самых маленьких: BFS 0-1

Новая постановка задачи

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

Решение

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

Реализация

Предполагается, что граф представлен в виде vector<vector<pair<int,int>>> edges, где edges[v] — массив ребер, исходящих из вершины v. Каждое ребро задается парой чисел — номером конечной вершины и весом.
Расстояния до вершин хранятся в vector<int> d, причем изначально все элементы этого массива — числа, заведомо большие, чем расстояния до всех вершин.

void BFS() {     // Инициализация     deque<int> q;     q.push_back(start);     d[start] = 0;     // Главный цикл     while (!q.empty())     {         // Достаем вершину         int v = q.front();         q.pop_front();         // Смотрим на всех ее соседей         for (int i = 0; i < (int)edges[v].size(); ++i)         {             // Если можно улучшить известное расстояние             if (d[edges[v][i].first] > d[v] + edges[v][i].second)             {                 // То улучшаем его и добавляем вершину в дек                 d[edges[v][i].first] = d[v] + edges[v][i].second;                 // Если ребро бесплатное, то в начало                 if (edges[v][i].second == 0)                 {                     q.push_front(edges[v][i].first);                 }                 // Иначе - в конец                 else                 {                     q.push_back(edges[v][i].first);                 }             }         }     } } 

Сложность алгоритма

Для каждого ребра и каждой вершины выполняется константное количество действий, поэтому временная сложность алгоритма — O(V+E).
Каждая вершина, очевидно, попадает в дек не более двух раз, поэтому количество используемой алгоритмом памяти — O(V).