今天写一个最短路题边权为 \(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\) 写就是了。
\(Easy!\)