#include<bits/stdc++.h>
//#define int long long
using namespace std;
int s,t,n;
class node {
	public:int rc,w;
};
vector<node> to[200001];
inline int SPFA() {
	array<int,200001> dis;
	for(int i=1; i<=n; i++) dis[i]=0x7fffffff;
	bitset<200001> vi;
	queue<int> q;
	dis[s]=0;
	vi[s]=1;
	q.push(s);
	int v,w,u;
	while(!q.empty()) {
		u=q.front();
		q.pop();
		vi[u]=0;
		for(int i=0; i<to[u].size(); i++) {
			v=to[u][i].rc;
			w=to[u][i].w;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				if(vi[v]==0) q.push(v),vi[v]=1;
			}
		}
	}
	return dis[t];
}
main() {
	array<int,200001> xx;
	array<int,200001> yy;
	cin>>n;
	s=1;
	t=n;
	for(int i=1; i<=n; i++) cin>>xx[i]>>yy[i];
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			int u=i,v=j,w;
		    w=min((xx[i]-xx[j]<0?-(xx[i]-xx[j]):xx[i]-xx[j]),(yy[i]-yy[j]<0?-(yy[i]-yy[j]):yy[i]-yy[j]));
			to[u].push_back({v,w});
			to[v].push_back({u,w});
		}
	}
	cout<<SPFA();
}

Description

Time limit: 1s

Memory limit:128M

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

Input 第一行包含一个正整数n，表示点数。

接下来n行，每行包含两个整数$x[i],y[i](0<=x[i],y[i]<=10^9)$，依次表示每个点的坐标。

Output 一个整数，即最小费用。

Sample Input

5

2 2

1 1

4 5

7 1

6 7

Sample Output

2

MLE，超了100KB