题意
略
数据范围:$1 \le n \le 50000$
题解
优先队列$\text{bfs}$,以移动的干草堆数升序
代码:
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int N=1000+10;
int n,sx,sy,x,y;
bool m[N][N];
bool vis[N][N];
int v[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
inline int bfs(){
priority_queue<pip,vector<pip>,greater<pip> > pq;
pq.push(mp(0,mp(sx,sy)));
vis[sx][sy]=1;
for(;!pq.empty();){
pip u=pq.top();
pq.pop();
int x=u.second.first,y=u.second.second;
if(x==0 && y==0)
return u.first;
for(int i=0;i<4;i++){
int nx=x+v[i][0],ny=y+v[i][1];
if(nx<0 || nx>N || ny<0 || ny>N || vis[nx][ny])
continue;
vis[nx][ny]=1;
pq.push(mp(u.first+m[nx][ny],mp(nx,ny)));
}
}
}
int main(){
scanf("%d%d%d",&n,&sx,&sy);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
m[x][y]=1;
}
printf("%d",bfs());
return 0;
}
版权属于:Pelom
本文链接:https://pelom.top/archives/114/
转载时须注明出处及本声明