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