0-1 BFS¶
what¶
边权值为可能有，也可能没有（由于 BFS 适用于权值为 1 的图，所以一般权值是 0 或 1），或者能够转化为这种边权值的最短路问题。
例如在走迷宫问题中，你可以花 1 个金币走 5 步，也可以不花金币走 1 步，这就可以用 0-1 BFS 解决。
01 BFS，又称双端队列 BFS，是一种仅适用于边权为 0/1 的情况（也即，存在或不存在）。
01 BFS 一般使用双端队列 deque 解决。
why¶
01 BFS 使用“0先1后”的优化方法来保证队列内有序。
也即：
- 若选择边权为 0 的边，则将结果储存在双端队列的前方。
- 若选择边权为 1 的边，则将结果储存在双端队列的后方。
01 BFS 具备着“第一次到某个点所需要的代价就是这个点的最小代价”的性质。
有序性的证明¶
证明：
初始时队列仅有一个元素 0，队列有序。
对于每一次操作：
我们记每一次操作时的队首为 x，取出后队列有序，且仅含 x,x+1。（可以试着去证明，这里默认都知道。）
- 选择 0，将 x 放入队首。
- 选择 1，将 x+1 放入队尾。
显然，此时队列里仅含 x,x+1 这两种元素，队列有序。
how¶
vector<int> d(n, INF);
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
int v = q.front();
q.pop_front();
for (auto edge : adj[v]) {
int u = edge.first;
int w = edge.second;
if (d[v] + w < d[u]) {
d[u] = d[v] + w;
if (w == 1)
q.push_back(u);
else
q.push_front(u);
}
}
}