meepo's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

    记得这当时是哪一个神犇的模拟赛。。。然而当时我不会做。。。

    今天下午打完然后RE。。。花了一节课调我的Spfa就是一直RE。。。后来网上题解一查发现这道题卡Spfa出题人你的节操呢。。。

    因为两个点之间的距离之和横纵坐标有关。。所以有很多边是没有用的。。。去掉这些边可以有效的加快程序的速度。。。然后就可以过了。。。具体的方法是按横坐标排序后相邻的两个点连边。。纵坐标也相同。。。然后用Heap+dij

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
struct data{int x,y,id;} p[N];
struct node{int x,y,s,next;} e[N<<4];
struct Data{int val,id;};
bool operator < (Data a,Data b){return a.val>b.val;}
int head[N],vis[N],dis[N],n,h,t,cnt,s;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
priority_queue <Data> Q;
bool cmpx(data a,data b){return a.x<b.x;}
bool cmpy(data a,data b){return a.y<b.y;}
void Insert(int x,int y,int s){
	e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
	e[cnt].next = head[x];head[x] = cnt;
}
int main(){
	n = read();
	for (int i=1;i<=n;i++) p[i].x = read(),p[i].y = read(),p[i].id = i;
	sort(p+1,p+1+n,cmpx);
	for (int i=1;i<n;i++) Insert(p[i].id,p[i+1].id,p[i+1].x-p[i].x),Insert(p[i+1].id,p[i].id,p[i+1].x-p[i].x);
	sort(p+1,p+1+n,cmpy);
	for (int i=1;i<n;i++) Insert(p[i].id,p[i+1].id,p[i+1].y-p[i].y),Insert(p[i+1].id,p[i].id,p[i+1].y-p[i].y);
	for (int i=2;i<=n;i++) dis[i] = 1e9;
	Q.push((Data){0,1});
	while (!Q.empty()){
		int now = Q.top().id;Q.pop();
		if (vis[now]) continue;
		vis[now] = 1;
		for (int i=head[now];i;i=e[i].next)
			if (dis[e[i].y]>dis[now]+e[i].s){dis[e[i].y] = dis[now]+e[i].s;Q.push((Data){dis[e[i].y],e[i].y});}
	}
	printf("%d",dis[n]);
}