今天写一个最短路题边权为 \(0\) 或 \(1\)，我说这不一眼 \(dij\) 么？结果题解区全部写的 \(O(n+m)\) 的 \(01bfs\) 。
好家伙我居然一直不知道这么个东西，花了一个小时看会了，写一下原理。
实现的方法很简单，就是一个双端队列，去 \(nm\) 的 \(deque\)，我有手，可以手写。
在这里讲一下正确性：
众所周知 \(dij\) 的优先队列是按距源点的距离排序的。
在一开始，设我们双端队列里的 \(dis\) 值为 \(0,0,0,1,1,1\)。
很明显，在访问到第一个 \(1\) 之前，你访问到的全是 \(dis=0\) 的点
而 \(dis=0\) 的点拓展出来的点 \(dis\) 不会大于 \(1\)。
也就是说，当这个队列中不存在 \(dis=0\) 的点时，队列的的 \(dis\) 情况一定是 \(1,1,1,1,\cdots\)。
以此类推，当这个队列中不存在 \(dis=x\) 的点时，队列的的 \(dis\) 情况一定是 \(x+1,x+1,x+1,x+1,\cdots\)。
真滴是很不错，其他的部分你直接按照 \(dij\) 写就是了。
忘了说一点，因为每次更新成功都会将点加入队列，所以最多会加入 \(O(m)\) 次。
这 \(m\) 次可能都是往前面加，也可能都是往后面加，所以双端队列大小申请为 \(2m\)，从 \(m\) 的位置开始。
\(Easy!\)
标签：dij,队列,双端,cdots,01bfs,dis From： https://www.cnblogs.com/yhy-trh/p/01bfs.html