这道题我们首先会想到优化建图；
线段树优化建图？不对不对；
那么就具体问题具体分析：
浅显的性质：有可能选择的边一定存在于按x或y排序的相邻的两个点之间；
那么O(n)建图，然后dijkstra就好了；
#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
class node{
public:
int x,y,id;
}points[200010];
bool cmp1(node x,node y){
return x.x<y.x;
}
bool cmp2(node x,node y){
return x.y<y.y;
}
int head[200010],cnt;
class littlestar{
public:
int to,nxt,w;
void add(int u,int v,int gg){
to=v; nxt=head[u];
head[u]=cnt; w=gg;
}
}star[800010];
priority_queue<pair<int,int> >qwq;
int dis[200010],vis[200010];
void dijkstra()
{
qwq.push(make_pair(0,1));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
while(qwq.size()){
int u=qwq.top().second;
qwq.pop();
if(vis[u]) continue;
vis[u]=1;
for(register int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
qwq.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
int n;
scanf("%d",&n);
inc(i,1,n) scanf("%d%d",&points[i].x,&points[i].y),points[i].id=i;
sort(points+1,points+1+n,cmp1);
inc(i,2,n){
star[++cnt].add(points[i-1].id,points[i].id,points[i].x-points[i-1].x);
star[++cnt].add(points[i].id,points[i-1].id,points[i].x-points[i-1].x);
}
sort(points+1,points+1+n,cmp2);
inc(i,2,n){
star[++cnt].add(points[i-1].id,points[i].id,points[i].y-points[i-1].y);
star[++cnt].add(points[i].id,points[i-1].id,points[i].y-points[i-1].y);
}
dijkstra();
cout<<dis[n];
}
/*
5
2 2
1 1
4 5
7 1
6 7
*/