简介

这个算法只适用于处理边权仅为 0 或 1 的图

相比于通用的 Dijkstra 算法，01BFS 的时间复杂度更优，能达到 O(V+E)（V是顶点数，E是边数），且实现起来更加轻简洁。

核心

Dijkstra 的性能瓶颈在于维护有序状态的优先队列（堆），其入队操作带有 $\log$ 级别的时间开销。而在 0-1 BFS 中，我们可以利用双端队列（Deque）来人工维护这种单调性：

• 权值为 0 的边：意味着发现了一条“免费”路径，该节点应通过 push_front 插入队首，确保它排在所有权值为 1 的节点之前被优先探索。
• 权值为 1 的边：遵循常规 BFS 逻辑，通过 push_back 插入队尾。

这种策略本质上是 Dijkstra 的特例：通过双端队列确保了队列中的距离序列始终满足非递减性质，从而规避了堆排序的开销。

实现细节

1. 更新时机与冗余检查：在普通 BFS 中，节点入队即标记 visited；但在 0-1 BFS 中，一个节点可能先被权 1 边发现，随后又被权 0 边刷新出更短距离。因此，建议在入队前判断 if (new_dist < dist[v])，只有当发现更优路径时才允许入队。
2. 出队检查：为了彻底消除冗余计算，节点出队时应检查当前距离是否仍为 dist 数组中的最优值，若已被之前的操作更新，则直接跳过。
3. 空间稳定性：在 0-1 BFS 下，每个节点最多只会被更新两次（一次由权 1 边触发，一次由权 0 边触发），这保证了算法在空间占用上的可控性。

示例题目

P4554 小明的游戏

#include <bits/stdc++.h>
#define endl "\n"
#define rep(i, a, b) for (i64 i = a; i <= b; i++)
#define lep(i, a, b) for (i64 i = a; i >= b; i--)
// #define MOD
using namespace std;
using i64 = int64_t;
using ui64 = uint64_t;
using vi64 = vector<i64>;

// static const i64 MOD = ;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    i64 n, m;
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;
        vector<string> go(n);
        rep(i, 0, n - 1) { cin >> go[i]; }
        i64 sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        vector<vector<i64>> d(n, vector<i64>(m, LLONG_MAX));
        deque<pair<i64,pair<i64, i64>>> dq;
        d[sx][sy] = 0;
        dq.push_back({0,{sx, sy}});
        while (dq.size()) {
            auto [a, b] = dq.front();
            auto [x,y]=b;
            dq.pop_front();
            if(a>d[x][y]) continue;
            for (i64 i = 0; i < 4; i++) {
                i64 nx = x + dx[i];
                i64 ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                i64 q = (go[x][y] != go[nx][ny]);
                if (d[x][y] + q < d[nx][ny]) {
                    d[nx][ny] = d[x][y] + q;
                    if (q) {
                        dq.push_back({d[nx][ny],{nx, ny}});
                    } else {
                        dq.push_front({d[nx][ny],{nx, ny}});
                    }
                }
            }
        }
        cout << d[ex][ey] << endl;
    }
    return 0;
}