/**************************************************************

     Problem: 4152

     User: Tunix

     Language: C++

     Result: Accepted

     Time:4304 ms

     Memory:27204 kb

 ****************************************************************/

 //BZOJ 4152

 #include<vector>

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 typedef long long LL;

 inline int getint(){

     int r=,v=; char ch=getchar();

     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;

     for(; isdigit(ch);ch=getchar()) v=v*-''+ch;

     return r*v;

 }

 const int N=2e5+,INF=~0u>>;

 /*******************template********************/

 int head[N],to[N<<],nxt[N<<],l[N<<],cnt;

 void add(int x,int y,int z){

     to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; l[cnt]=z;

     to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; l[cnt]=z;

 }

 int n,d[N];

 struct node{

     int x,y,num;

 }a[N];

 bool cmpx(node a,node b){return a.x<b.x;}

 bool cmpy(node a,node b){return a.y<b.y;}

 typedef pair<int,int> pii;

 #define mp make_pair

 #define se second

 priority_queue<pii,vector<pii>,greater<pii> >Q;

 bool vis[N];

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("4152.in","r",stdin);

     freopen("4152.out","w",stdout);

 #endif

     n=getint();

     F(i,,n) a[i].x=getint(),a[i].y=getint(),a[i].num=i;

     sort(a+,a+n+,cmpx);

     F(i,,n-) add(a[i].num,a[i+].num,a[i+].x-a[i].x);

     sort(a+,a+n+,cmpy);

     F(i,,n-) add(a[i].num,a[i+].num,a[i+].y-a[i].y);

     F(i,,n) d[i]=INF;

     d[]=;

     Q.push(mp(,));

     while(!Q.empty()){

         int x=Q.top().se; Q.pop();

         if (vis[x]) continue;

         vis[x]=;

         for(int i=head[x];i;i=nxt[i])

             if (d[to[i]]>d[x]+l[i]){

                 d[to[i]]=d[x]+l[i];

                 Q.push(mp(d[to[i]],to[i]));

             }

     }

     printf("%d\n",d[n]);

     return ;

 }

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

一个整数，即最小费用。