事实上每次走到横坐标或纵坐标最接近的点一定可以取得最优方案。于是这样连边跑最短路就可以了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 200010 int n,p[N],d[N],t=0; bool flag[N]; struct point{int x,y,i; }a[N]; struct data{int to,nxt,len; }edge[N<<2]; struct data2 { int x,d; bool operator <(const data2&a) const { return d>a.d; } }; priority_queue<data2> q; void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} void dijkstra() { while (!q.empty()) q.pop(); for (int i=2;i<=n;i++) d[i]=1000000001;q.push((data2){1,0}); memset(flag,0,sizeof(flag)); for (int i=1;i<=n;i++) { while (!q.empty()&&flag[q.top().x]) q.pop(); if (q.empty()) break; data2 v=q.top();q.pop(); flag[v.x]=1; for (int j=p[v.x];j;j=edge[j].nxt) if (v.d+edge[j].len<d[edge[j].to]) { d[edge[j].to]=v.d+edge[j].len; q.push((data2){edge[j].to,d[edge[j].to]}); } } } bool cmp1(const point&a,const point&b) { return a.x<b.x; } bool cmp2(const point&a,const point&b) { return a.y<b.y; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4152.in","r",stdin); freopen("bzoj4152.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].i=i; sort(a+1,a+n+1,cmp1); for (int i=1;i<n;i++) addedge(a[i].i,a[i+1].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y))), addedge(a[i+1].i,a[i].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y))); sort(a+1,a+n+1,cmp2); for (int i=1;i<n;i++) addedge(a[i].i,a[i+1].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y))), addedge(a[i+1].i,a[i].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y))); dijkstra(); cout<<d[n]; return 0; }