双端队列bfs

文章目录
一、双端队列bfs二、双端队列的知识点三、例题Acwing175. 电路维修例题Acwing340. 通信线路

一、双端队列bfs
双端队列bfs只适用于边权只为 0或1 的无向图，在扩展的时候如果边权为 0 则插入队头，边权为 1 时插入队尾，这样一来，我们就能保证，在任意时刻广搜队列中的节点对应的距离值都具有“两段性”，和“单调性“每个节点可能会更新（入队）多次，但是它第一次出队时，就能得到从起点到该节点的最短距离（因为会优先走边权为 0 的点），之后取出可以直接忽略。
二、双端队列的知识点
assign 重新给容器分配元素 push_back 向容器末尾插入元素 push_front 向元素开头插入元素 pop_back 删除末尾元素 pop_front 删除开头元素 insert 向指定位置插入元素，返回值为指向最后一个插入位置的迭代器 erase 删除元素 swap 交

双端队列bfs最先出现在Python成神之路。