题目传送门

Part 0.5 说在前面

• 此题解借鉴冯易菜鸡的题解。

• 文章中的三张图都由 TA 提供。

Part 1 拆点

• 首先，我们会发现激光经过一个点时会有四种状态。
• 从上面经过、从左边经过、从右边经过、从下面经过。
• 于是乎，把一个点拆成四个点，分别代表激光从四个方向经过。
• 并把四个点连上。

• 那么我们可以把放反射镜看成两个相邻的点之间的转移，边权为 $1$。

//给四个点标上号
#define e1 i*4+1
#define e2 i*4+2
#define e3 i*4+3
#define e4 i*4+4

for(int i=1;i<=n+2;i++){
	Add(e1,e2,1);
	Add(e1,e3,1);
	Add(e2,e4,1);
	Add(e3,e4,1);
}

• 再把直接穿过看成两边的点之间的转移，边权为 $0$。

for(int i=1;i<=n+2;i++){
    Add(e1,e4,0);
    Add(e2,e3,0);
}

• 那么激光从 $x$ 栅栏到 $y$ 栅栏横向穿过，就可以看成 $x$ 的右边点到 $y$ 的左边点的转移。

• 纵向同理。

bool Cmpx(Node x,Node y){
	if(x.x-y.x) return x.x<y.x;
	return x.y<y.y;
}	
bool Cmpy(Node x,Node y){
	if(x.y-y.y) return x.y<y.y;
	return x.x<y.x;
}

sort(a+1,a+n+3,Cmpx);
for(int i=1;i<n+2;i++)
	if(a[i].x==a[i+1].x)
		Add(a[i].id*4+3,a[i+1].id*4+2,0);
sort(a+1,a+n+3,Cmpy);
for(int i=1;i<n+2;i++)
	if(a[i].y==a[i+1].y)
		Add(a[i].id*4+4,a[i+1].id*4+1,0);

• 要注意的是，起点和终点也要拆成四个点，所以代码里写的是 $n+2$。

• 建完图就是这样。

• 最后再给起点和终点连一个超级起点和超级终点。

s=0; t=(n+2)*4+5;

Add(s,(n+1)*4+1,0);
Add(s,(n+1)*4+2,0);
Add(s,(n+1)*4+3,0);
Add(s,(n+1)*4+4,0);
Add(t,(n+2)*4+1,0);
Add(t,(n+2)*4+2,0);
Add(t,(n+2)*4+3,0);
Add(t,(n+2)*4+4,0);

• 最后跑一遍 Dijkstra 即可。

int dis[N<<2],vis[N<<2];
void Dijkstra(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<Edge>q;
	dis[s]=0;
	q.push({s,0});
	while(!q.empty()){
		int u=q.top().v; q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(Edge edge:mp[u]){
			int v=edge.v,w=edge.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}

Part 2 总代码

#include<bits/stdc++.h>
#define int long long
#define e1 i*4+1
#define e2 i*4+2
#define e3 i*4+3
#define e4 i*4+4
using namespace std;
inline int read(){
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}
const int N=1e5+50;
int n,s,t;
struct Node{
	int x,y,id;
}a[N];
struct Edge{
	int v,w;
	bool operator<(const Edge x)const{
		return w>x.w;
	}
};
vector<Edge>mp[N<<2];
bool Cmpx(Node x,Node y){
	if(x.x-y.x) return x.x<y.x;
	return x.y<y.y;
}	
bool Cmpy(Node x,Node y){
	if(x.y-y.y) return x.y<y.y;
	return x.x<y.x;
}
void Add(int u,int v,int w){
	mp[u].push_back({v,w});
	mp[v].push_back({u,w});
}
int dis[N<<2],vis[N<<2];
void Dijkstra(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<Edge>q;
	dis[s]=0;
	q.push({s,0});
	while(!q.empty()){
		int u=q.top().v; q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(Edge edge:mp[u]){
			int v=edge.v,w=edge.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
signed main(){
	n=read(); s=0; t=(n+2)*4+5;
	a[n+1]={read(),read(),n+1};
	a[n+2]={read(),read(),n+2};
	for(int i=1;i<=n;i++) a[i]={read(),read(),i};
	for(int i=1;i<=n+2;i++){
		Add(e1,e2,1);
		Add(e1,e3,1);
		Add(e2,e4,1);
		Add(e3,e4,1);
		Add(e1,e4,0);
		Add(e2,e3,0);
	}
	Add(s,(n+1)*4+1,0);
	Add(s,(n+1)*4+2,0);
	Add(s,(n+1)*4+3,0);
	Add(s,(n+1)*4+4,0);
	Add(t,(n+2)*4+1,0);
	Add(t,(n+2)*4+2,0);
	Add(t,(n+2)*4+3,0);
	Add(t,(n+2)*4+4,0);
	sort(a+1,a+n+3,Cmpx);
	for(int i=1;i<n+2;i++)
		if(a[i].x==a[i+1].x)
			Add(a[i].id*4+3,a[i+1].id*4+2,0);
	sort(a+1,a+n+3,Cmpy);
	for(int i=1;i<n+2;i++)
		if(a[i].y==a[i+1].y)
			Add(a[i].id*4+4,a[i+1].id*4+1,0);
	Dijkstra();
	if(dis[t]>1e17) cout<<-1;
	else cout<<dis[t];
	return 0;
}

Part 3 结尾

• $\textcolor{black}{复制}$一时爽。
• $\textcolor{brown}{棕名}$两行泪。

AC链接