比赛 |
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;
}