代码在线求调

#include <bits/stdc++.h>//万能头文件
using namespace std;
//#define SIZE (1<<20)
//char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
//#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
inline long long read(){//快读
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
#define int long long
const int N=2e5+10;
int m,n,k;

struct rooms{int x,y,id;}r[N];
bool cmp1(rooms a,rooms b){return a.x<b.x;}
bool cmp2(rooms a,rooms b){return a.y<b.y;}

struct edge{
	int to,next,value;
}e[N<<2];
int head[N<<1],edge_cnt;
void addedge(int u,int v,int w){
	e[++edge_cnt]=(edge){v,head[u],w};
	head[u]=edge_cnt;
} 

priority_queue<pair<int,int> > q;
int dis[N],vis[N];
void dij(int n){
	memset(dis,63,sizeof(dis)); 
	memset(vis,0,sizeof(vis));
	q.push(make_pair(0,n));
	while(!q.empty()){
		int du=-q.top().first,u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;dis[u]=du;
		for(int i=head[u];i;i=e[i].next){
			q.push(make_pair(-du-e[i].value,e[i].to));
		}
	}
}
bool flag=false;
signed main(){
//	freopen("house.in","r",stdin);
//	freopen("house.out","w",stdout);
	m=read(),n=read(),k=read();
	for(int i=1;i<=k;i++){
		r[i].x=read(),r[i].y=read(),r[i].id=i;
		if(r[i].x==1&&r[i].y==1)flag=true;
	}
	r[k+1].x=1,r[k+1].y=1,r[k+1].id=k+1;
	r[k+2].x=m,r[k+2].y=n,r[k+2].id=k+2;
//	for(int i=1;i<=k+2;i++)printf("%d,%d:%d\n",r[i].x,r[i].y,r[i].id); 
	r[0].x=-1,r[0].y=-1;
	//不+k记录行，+k记录列
	sort(r+1,r+1+k+2,cmp1);
//	for(int i=1;i<=k+2;i++)cerr << r[i].x << " " << r[i].y << "\n";
	for(int i=1;i<=k+2;i++){ 
		if(r[i].x==r[i-1].x){
//			printf("%d,%d:%d -> %d,%d:%d\n",r[i].x,r[i].y,r[i].id,r[i-1].x,r[i-1].y,r[i-1].id);
			addedge(r[i].id,r[i-1].id+k+2,abs(r[i].y-r[i-1].y)+1);
			addedge(r[i-1].id,r[i].id+k+2,abs(r[i].y-r[i-1].y)+1);
		}
	}
	sort(r+1,r+1+k+2,cmp2);
//	for(int i=1;i<=k+2;i++)cerr << r[i].x << " " << r[i].y << "\n";
	for(int i=1;i<=k+2;i++){
		if(r[i].y==r[i-1].y){
			addedge(r[i].id+k+2,r[i-1].id,abs(r[i].x-r[i-1].x)+1);
			addedge(r[i-1].id+k+2,r[i].id,abs(r[i].x-r[i-1].x)+1);
		}
	}
//	for(int i=1;i<=2*k+4;i++){
//		for(int j=head[i];j;j=e[j].next){
//			cerr << i << "->" << e[j].to << ":" << e[j].value << "\n";
//		}
//	}
	dij(k+1);
	int ans=4557430888798830399;
//	for(int i=1;i<=2*k+4;i++)cerr << dis[i] << " ";
	ans=min({ans,dis[k+2],dis[k+2+k+2]});
	if(flag){
		dij(k+1+k+2);
		ans=min({ans,dis[k+2],dis[k+2+k+2]});
	}
	if(ans!=4557430888798830399)cout << ans-1;
	else cout << -1;
	return 0;
}