问题引入
对于边权为 0/1 的图 \(G=(V,E)\)，求解其最短路。（注意这里的 1 并不一定就是 1，只是反映有无权值）
ps. 一下称该类图为 0-1 图。
求解
一般图一般有 Dijkstra 和 SPFA。
但对于 0-1 图这样特殊的图，\(O(m\log m)\) 的 Dijkstra 就显的冗余了。
问题主要在于，每次 dis 的更新波动很小，用 优先队列 维护的 Dijkstra 就大材小用了。
考虑直接用 双端队列 代替 优先队列。
具体地，把没有权值的边扩展到的点放到队首，有权值的边扩展到的点放到队尾。
这样即可保证像普通 bfs 一样整个队列队首到队尾权值单调不下降。
时间复杂度
\(O(n+m)\)。
标签：队尾,队列,队首,bfs,Dijkstra,权值 From： https://www.cnblogs.com/cqbz-dxm/p/17760131.html