比赛 |
2025暑期集训第5场图论专场 |
评测结果 |
AAAAAAAAAAA |
题目名称 |
激光 |
最终得分 |
100 |
用户昵称 |
KKZH |
运行时间 |
0.846 s |
代码语言 |
C++ |
内存使用 |
22.27 MiB |
提交时间 |
2025-07-09 11:57:33 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int n,sx,sy,ex,ey,cnt,cntx,cnty;
int head[N],dis[N],a[N][2],firx[N],firy[N];
map <int,int> mpx,mpy;
struct node1{
int num,len;
friend bool operator<(const node1 a,const node1 b){
return a.len>b.len;
}
};
struct node{
int next,to,len;
}ed[N];
priority_queue <node1> q;
void add(int x,int y,int z){
ed[++cnt].next=head[x];
ed[cnt].to=y;
ed[cnt].len=z;
head[x]=cnt;
}
void dij(){
while(!q.empty()){
int d = q.top().len;
int x=q.top().num;
q.pop();
if (d != dis[x]) continue;
for(int i=head[x];i!=-1;i=ed[i].next){
int y=ed[i].to,z=ed[i].len;
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;
q.push({y,dis[y]});
}
}
}
}
int main(){
freopen("lasers.in","r",stdin);
freopen("lasers.out","w",stdout);
memset(dis,0x3f,sizeof(dis));
memset(head,-1,sizeof(head));
cin>>n>>sx>>sy>>ex>>ey;
int x,y;
a[n+1][0]=sx;
a[n+1][1]=sy;
a[n+2][0]=ex;
a[n+2][1]=ey;
for(int i=1;i<=n;i++)
cin>>a[i][0]>>a[i][1];
n=n+2;
for (int i = 1; i <= n; i++) {
int x = a[i][0], y = a[i][1];
if (mpx.find(x) == mpx.end()) {
mpx[x] = ++cntx;
firx[cntx] = i;
} else {
int j = firx[mpx[x]];
add(i + n, j + n, 0);
add(j + n, i + n, 0);
}
if (mpy.find(y) == mpy.end()) {
mpy[y] = ++cnty;
firy[cnty] = i;
} else {
int j = firy[mpy[y]];
add(i, j, 0);
add(j, i, 0);
}
}
for(int i=1;i<=n;i++){
add(i,i+n,1);
add(i+n,i,1);
}
dis[n+n-1]=0;
dis[n-1]=0;
q.push({n-1,0});
q.push({2*n-1,0});
dij();
int ans=min(dis[n],dis[2*n]);
if(ans!=1061109567)
cout<<ans;
else cout<<-1;
return 0;
}