AcWing 2019. 拖拉机（双端BFS）

题目链接

https://www.acwing.com/problem/content/2021/

思路

一个有0代价和1代价边权的最短路，我们用双端队列将0和1边权用一个双端队列分开存储，然后进行一个类迪杰斯特拉的最短路即可,值得注意的是，这个二维平面是无限大的，但是我们只需要多使用一层（这一圈都是空的）就好了，因为效果都一样，详情请看代码

代码

#include 
using namespace std;

const int N = 1e3+10;

bool mp[N][N];
int dis[N][N];
bool vis[N][N];
typedef pair  PII;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

bool check(int x,int y) {
	if(x >= 0 && x = 0 && y >n>>sx>>sy;
	int x,y;
	for(int i = 1;i >x>>y;
		mp[x][y] = true;
	}
	cout