- O1BFS
- 简介
- BFS?
- 算法思想
- 识破！
- 坑！
- 例题
- 电路维修
- Codeforces 1063B - Labyrinth
O1BFS
简介
这个算法只适用于处理边权仅为 0 或 1 的图
相比于通用的 Dijkstra 算法，01BFS 的时间复杂度更优，能达到 \(O(V + E)\)（\(V\) 是顶点数，\(E\) 是边数），且实现起来更加轻简洁。
BFS?
我们还可以尝试用 bfs 来解决这个问题，只需要正常 bfs，输出第一个到达终点的路径即可。
但是这样有个问题，由于点的花费不相等，但是 bfs 我们把所有的从一个任意点到另一个任意点的操作视为等价，所以第一个到达的只是距离上最短的。
有的时候，绕路的花费更少。
所以这个想法就被证伪了。
算法思想
Dijkstra的算法瓶颈在于优先队列
优先队列是带log的
而这个BFS有一个很好的方法：
如果是边权为0的，那么就优先去选
反之亦然
换句话说：如果你发现一条“免费”（权重为 0）的路，你应该立刻去探索它，而不是等排在后面的“收费”路走完。
你可以把 01BFS 想象成一个阉割版的 Dijkstra：
- Dijkstra 用优先队列（大顶堆/小顶堆）来维护单调性。
- 01BFS 用双端队列（Deque）来维护单调性。
识破！
并不是所有题目都会直接告诉你边权是 0 或 1。常见的变形包括：
- 网格图： 某些格子可以直接走（权 0），某些格子需要“破坏”或“转向”才能走（权 1）。
- 开关问题： 状态转换不需要代价（权 0），转换需要某种操作（权 1）。
坑！
重复入队： 虽然 01BFS 下每个节点最多入队两次（或者通过判断距离只入队一次），但出队时仍要检查当前距离是否是最优，以防冗余计算。
与 Dijkstra 的区别： 01BFS 是 Dijkstra 在特殊边权下的特例。如果边权出现了 2 或更大的数，请务必换回 Dijkstra 或优先队列。
入队 vs 出队更新： 在普通 BFS 中，我们在节点入队时标记 visited；但在 01BFS 中，建议在出队时确认。或者，如果你在入队时更新 dist，一定要确保：只有当 new_dist < dist[v] 时才放入 Deque。
空间优化： 在 01BFS 中，一个节点最多会被更新两次（一次被权 1 的边更新，一次被权 0 的边更新）。
例题
电路维修
电路板上的元件是 \ 或 /，你想从左上角走到右下角。
思考🤔
如果当前的电线方向符合你的走法，权值为 0；如果需要旋转电线，权值为 1。
🤯🤯
Codeforces 1063B - Labyrinth
这题不是求总最短路，而是对“向左走”和“向右走”的次数分别有上限。
我们可以尝试把“向左走”作为权值 1，其他方向（上下右）作为权值 0。
这题最巧bian妙tai的地方在于：你只需要维护“向左走”的最少步数。
假设从起点到某个格子 \((i, j)\)，向左走了 \(x\) 步，向右走了 \(y\) 步。
我们可以得到两个方程：
- \(y - x = j - c\) （水平净位移 = 当前列 - 起点列）
- \(y = x + j - c\)
所以，只要 \(x\)（向左走的步数） 最小，\(y\)（向右走的步数） 也就随之最小。
- 如果向左走 \(x \le L\) 且 向右走 \((x + j - c) \le R\)，该格子就是可达的。
完结撒花！！