01BFS学习笔记
306 字
2 分钟
01BFS学习笔记
本人随机跳题到了一道看起来是最短路的题,但是本人并不想去暴力建图懒,发现如果抽象成一张图的话边权只有 或者 ,于是去学了个01BFS。
什么是01BFS呢,其实这是一种最短路的优化,我们都知道BFS要用到queue来维护正确性,但是这在找边权不相等的最短路里就很难受,所以我们需要给他规定一个转移顺序。
我们把queue换成deque,如果这条边边权是1的话就放在队尾,否则放在队首,参考dij里priority_queue的证明,这其实就是找到性质手动模拟了一个优先队列,并且我们的复杂度是优秀的 ,以为少了一个堆的log,就很优秀。
当然适用范围有点窄,只能在边权为 和一种其他正数中使用。
参考题目:P1849 [USACO12MAR] Tractor S
#include<bits/stdc++.h>using namespace std;const int N=1005;int n,sx,sy,a[N][N],t[N][N];int stx[6]{-1,0,1,0};int sty[6]{0,-1,0,1};deque<pair<int,int>>q;void BFS(){ q.push_front(make_pair(sx,sy)); memset(t,-1,sizeof t); t[sx][sy]=0; while(q.size()){ int x=q.front().first; int y=q.front().second; q.pop_front(); for(int i=0;i<4;i++){ int tx,ty; tx=x+stx[i]; ty=y+sty[i]; if(tx<0||tx>=N) continue; if(ty<0||ty>=N) continue; if(t[tx][ty]!=-1) continue; if(a[tx][ty]){ t[tx][ty]=t[x][y]+1; q.push_back(make_pair(tx,ty)); }else{ t[tx][ty]=t[x][y]; q.push_front(make_pair(tx,ty)); } } }}
int main(){ scanf("%d%d%d",&n,&sx,&sy); for(int i=1;i<=n;i++){ int s1,s2; scanf("%d%d",&s1,&s2); a[s1][s2]=1; } BFS(); printf("%d",t[0][0]); return 0;}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!
相关文章智能推荐
1
01分数规划学习笔记
算法竞赛2023-11-16
2
cs224n学习笔记
人工智能2026-01-18
3
关于dp状态转移方程的设计4
算法竞赛2026-07-18
4
基础神经网络学习笔记
人工智能2025-11-02
5
关于动态规划的转移1
算法竞赛2023-11-01
随机文章随机推荐

