C++(clang++11) 解法, 执行用时: 56ms, 内存消耗: 8732K, 提交时间: 2020-10-23 16:24:16

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
const int N=2e5+5,M=N<<1;
int n,a,b,c,d;
int x[N],y[N],x2[N],y2[N],cnt1,cnt2;
int head[N],to[M],nxt[M],e[M],idx,dis[N],vis[N];

void add(int x,int y,int z)//建边 
{
	to[++idx]=y;nxt[idx]=head[x];e[idx]=z;head[x]=idx;
}

int askx(int x)//查询原来的横坐标的值所对应的离散后的值 
{
	return lower_bound(x2+1,x2+cnt1+1,x)-x2;
}
int asky(int y)//查询原来的纵坐标的值所对应的离散后的值 
{
	return lower_bound(y2+1,y2+cnt2+1,y)-y2;
}

void spfa()
{
	queue<int>q;
	memset(dis,0x3f,sizeof dis);
	q.push(askx(a));q.push(asky(b)+cnt1);//最初的起点从行射出去和从列射出去都要考虑 
	dis[askx(a)]=dis[asky(b)+cnt1]=0;
	vis[askx(a)]=vis[asky(b)+cnt1]=1;
	while(q.size())
	{
		int x=q.front();q.pop();vis[x]=0;
		for(int i=head[x];i;i=nxt[i])
		{
			int y=to[i],z=e[i];
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				if(!vis[y]) q.push(y),vis[y]=1;
			}
		}
	}
}
int main()
{
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	x[n+1]=a;y[n+1]=b;//别忘了把起点和终点加进来 
	x[n+2]=c;y[n+2]=d;
	n+=2;
	memcpy(x2,x,sizeof x);//x2和y2是临时数组用于离散化 
	memcpy(y2,y,sizeof y);
	sort(x2+1,x2+1+n);
	sort(y2+1,y2+1+n);
	cnt1=unique(x2+1,x2+1+n)-x2-1;
	cnt2=unique(y2+1,y2+1+n)-y2-1;
	
	for(int i=1;i<=n;i++)//防止横纵坐标离散值编号冲突,给纵坐标的离散值加上cnt1 
	{
		add(askx(x[i]),asky(y[i])+cnt1,1);
		add(asky(y[i])+cnt1,askx(x[i]),1);
	}
	spfa();
	printf("%d",min(dis[askx(c)],dis[asky(d)+cnt1]));//输出答案,是从行转移过来更优还是从列转移过来更优 	
}