寒假每日一题 2022/1/5 双端bfs

题目 题意: 在二维坐标系中，初始位于(sx,sy)处，求到达原点(0,0)的最小花费。规定走平地花费为0，走一个障碍花费为1。给定n个barrier坐标(x,y)，其余为平地. 思路: 双端bfs模板题。本题的实质是求一个图最短路，但是大概有n^2个边。用堆优化的Dij时间复杂度也很高。而双端bfs恰好可以解决此类问题，图中的边权均为0或1。只需要花O(n)的时间即可，n是点的总个数。  基本思想与队列bfs一致。只是更新时，通过边权为0的边更新的点放到队首;而通过边权为1的边更新的点放到队尾。 时间复杂度: O(n) 代码:

// Problem: 拖拉机
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2021/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i