网站首页
编程语言
数据库
系统相关
其他分享
编程问答
01BFS
2024-09-17
01BFS
P4554小明的游戏大部分bfs题都可以用最短路做,而最短路中dijkstra用堆优化保证权值小的优先操作,而这题权值只有01两种,所以用01bfs,具体用deque操作,增加权值为0时(同色),放到队头,增加的权值为1时(异色),放到队尾,相当于直接\(O(1)\)排序好了。#include<bits/stdc++.h>us
2024-07-08
01bfs
针对一类特殊图求最短路,如果边权只有01则可以使用双端队列代替堆,将最短路的时间复杂度从\(O(nlogn)\)降为\(O(n)\)。原理:每次所走边边权为0则放队首,边权为1则放队尾。题目1#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definepiipair<int,int>#