什么叫分层图最短路，我不会/kk

感觉自己做法和其他题解不大一样所以过来发篇题解了。

未刻意卡常拿下最优解

题目大意

就是说给你一个 $n \times n$ 的网格图和 $m$ 个可换乘点，然后你只能在同一行或同一列（如果在行上移动，就不能在列上移动；反之同理）上移动，除非这个点是可以换乘的。每次走一格花费 $2$ 费，换乘花费 $1$ 费，求从 $(sx,sy)$ 到 $(fx,fy)$ 的最小费用。

其中:$n \leqslant 20000,m \leqslant 100000$

分析

可以发现如果对于每个格点都存储信息是不可行的，我们考虑优化空间：发现我们的路径实际上就是一直冲，然后只有在部分换乘点转弯，所以我们可以把换乘点联系起来，在换乘点之间跑最短路。

具体做法

那么具体怎么做呢，我们考虑对于每行和每列开领接表，存储这一行或这一列上，存在的换乘点的编号。然后可以把起始点也看做换乘点。然后跑最短路的时候就直接通过两点的距离$\times 2 + 1$ 来转移最短路距离(因为我们去换乘点便是为了转弯)，最后输出 $dis[$ 终点编号 $]-1$即可（$-1$ 是为了把在终点转弯的费用减掉）。最后注意数组大小别开错就行了。（我因为这个WA了一发）

那么看代码吧！

Code:

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
	return s*f;
}
inline int dist(int x,int y){
	return x>y?x-y:y-x;
}
const int INF=1e9;
const int N=20000+3;
const int M=100002+3;
struct node{
	int x,y;
}p[M];
int n,m;
int sx,sy,fx,fy;
queue<int>q;
int dis[M];
bool inq[M];
vector<int>h[N],l[N];
inline void SPFA(){//最短路
	q.push(1);inq[1]=1;
	for(int i=1;i<=m+2;++i){
		dis[i]=INF;
	}
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();q.pop();inq[u]=0;
		int lena=h[p[u].x].size(),lenb=l[p[u].y].size();
		//考虑转弯，可以发现往回走是不优的，但是都不违反题意，所以行列都跑一遍也没事。
		for(int i=0;i<lena;++i){
			int v=h[p[u].x][i],val=dist(p[v].y,p[u].y)*2+1;//费用计算
			if(v==u) continue;
			if(dis[v]>=dis[u]+val){
				dis[v]=dis[u]+val;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
		for(int i=0;i<lenb;++i){
			int v=l[p[u].y][i],val=dist(p[v].x,p[u].x)*2+1;
			if(u==v) continue;
			if(dis[v]>=dis[u]+val){
				dis[v]=dis[u]+val;
				if(!inq[v]){
					q.push(v);
					inq[v]=1;
				}
			}
		}
	}
}
int main(){
	n=read();m=read();
	for(int i=2;i<=m+1;++i){
		p[i].x=read();p[i].y=read();
		h[p[i].x].push_back(i);
		l[p[i].y].push_back(i);//类似领接表的东西
	}
	sx=read();sy=read();fx=read();fy=read();
	h[sx].push_back(1);l[sy].push_back(1);
	h[fx].push_back(m+2);l[fy].push_back(m+2);//把起始点当做换乘点
	p[1]={sx,sy};p[m+2]={fx,fy};
	SPFA();
	if(dis[m+2]!=INF) printf("%d\n",dis[m+2]-1);//除去多余的最后一次转弯费用
	else printf("-1\n");//无法到达输-1
	return 0;
}

似乎比其他题解的做法简单一些？