比赛 2025暑期集训第5场图论专场 评测结果 AAAAAAAAAAA
题目名称 激光 最终得分 100
用户昵称 徐诗畅 运行时间 0.644 s
代码语言 C++ 内存使用 22.42 MiB
提交时间 2025-07-09 11:23:50
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,xl,yl,xb,yb,head[N<<5],cnt,dis[N<<5],vis[N<<5];
struct str{int x,y,id;}a[N];
struct edge{int v,w,next;}e[N<<5];
void addedge(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
bool cmp1(str x,str y){
	if(x.x==y.x) return x.y<y.y;
	return x.x<y.x;
}
bool cmp2(str x,str y){
	if(x.y==y.y) return x.x<y.x;
	return x.y<y.y;
}
struct node{
	int u,d;
	bool operator<(const node&r) const{
		return d>r.d;
	}
};
int main(){
	freopen("lasers.in","r",stdin);
	freopen("lasers.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&xl,&yl,&xb,&yb);
	a[n+1].x=xl; a[n+1].y=yl;
	a[n+2].x=xb; a[n+2].y=yb;
	for(int i = 1;i<=n+2;i++){
		if(i<=n) scanf("%d%d",&a[i].x,&a[i].y); a[i].id=i;
		addedge(4*i+1,4*i+2,1); addedge(4*i+2,4*i+1,1);
		addedge(4*i+2,4*i+3,1); addedge(4*i+3,4*i+2,1);
		addedge(4*i+3,4*i+4,1); addedge(4*i+4,4*i+3,1);
		addedge(4*i+4,4*i+1,1); addedge(4*i+1,4*i+4,1);
		addedge(4*i+1,4*i+3,0); addedge(4*i+3,4*i+1,0);
		addedge(4*i+2,4*i+4,0); addedge(4*i+4,4*i+2,0);
	}
	sort(a+1,a+3+n,cmp1);
	for(int i = 1;i<=n+2;i++){if(a[i].x==a[i-1].x) addedge(4*(a[i-1].id)+1,4*a[i].id+3,0),addedge(4*a[i].id+3,4*(a[i-1].id)+1,0);}
	sort(a+1,a+3+n,cmp2);
	for(int i = 1;i<=n+2;i++){if(a[i].y==a[i-1].y) addedge(4*a[i].id+2,4*(a[i-1].id)+4,0),addedge(4*(a[i-1].id)+4,4*a[i].id+2,0);}
	addedge(1,4*(n+1)+1,0); addedge(1,4*(n+1)+2,0); addedge(1,4*(n+1)+3,0); addedge(1,4*(n+1)+4,0);
	addedge(4*(n+2)+1,2,0); addedge(4*(n+2)+2,2,0); addedge(4*(n+2)+3,2,0); addedge(4*(n+2)+4,2,0);
	priority_queue<node> q;
	memset(dis,0x3f3f3f3f,sizeof(dis)); dis[1]=0;
	q.push(node{1,0});
	while(!q.empty()){
		int u = q.top().u; q.pop();
		if(vis[u]) continue; vis[u]=1;
		for(int i = head[u];i;i=e[i].next){
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				q.push(node{v,dis[v]});
			}
		}
	}
	if(dis[2]>n) cout<<"-1";
	else printf("%d",dis[2]);
	return 0;
}