0-1BFS

求单源最短路径，边权有的为0，有的为1。
一般的BFS，每个边的边权都为1，保证广度优先搜索正确性的基础在于：对于源点 s 以及任意两个节点 u 和 v，如果dist[u]< dist[v]。那么节点 u 一定会比节点 v 先被取出队列。在常规的广度优先搜索中，我们使用队列作为维护节点的数据结构，就保证了从队列中取出的节点，它们与源点之间的距离是单调递增的。然而如果边权可能为 0，就会出现先将边权值为1的点加入队列再将边权值为0的点加入队列，这样在取出队列时，到源点之间的距离便不是单调递增的了，违反了广度优先搜索正确性的基础。于是我们用双向队列来作为维护节点的数据结构，当权值为0时，将其加入队首，当权值为1时，将其加入队尾。这样以来，我们保证了任意时刻从队首到队尾的所有节点，它们与源点之间的距离是单调递增的，即从队列中取出的节点与源点之间的距离同样是单调递增的。
例题：https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/
代码:

class Solution {
public:
    const int inf =INT_MAX/2;
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size();
        int n =grid[0].size();
        vector<vector<int>>dist(m,vector<int>(n,inf));
        deque<pair<int,int>>dq;
        dq.push_front({0,0});//起点放入队列
        dist[0][0] =0;
        while(!dq.empty())
        {
            auto [x,y] = dq.front();
            dq.pop_front();
            for(int i=0;i<4;i++)
            {
                int nx= x+dx[i];
                int ny = y+dy[i];
                if(nx>=0 && nx<m &&ny>=0 &&ny<n)
                {
                    int w = grid[nx][ny];//获取权值
                    if(dist[x][y]+w<dist[nx][ny])//若存在更短路径则更新权值。
                    {
                        dist[nx][ny] = dist[x][y]+w;
                        if(w==0)dq.push_front({nx,ny});//若权值为0放入队首，否则放入队尾。
                        else dq.push_back({nx,ny});
                    }
                }
            }
        }
        return dist[m-1][n-1];
    }
};