首先按照x,y分别排序相邻的连边然后跑最短路,这个应该是显然的,不知道用了什么卡SPFA的方法,必须用堆+Dij
//coder : davidwang #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <bitset> #include <deque> using namespace std; #define LL long long #define X first #define Y second template<typename T> inline T sqr(const T &x){ return x*x; } inline int read() { int ret=0,f=1; char ch; for (ch=getchar();ch<'0' || ch>'9';ch=getchar()) if (ch=='-') f=-f; for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-'0'; return ret*f; } const int N = 200010; const LL inf = 1LL<<60; struct point{ int x,y,pos; }a[N]; int start[N],next[N<<2],to[N<<2],len[N<<2],cnt; struct node{ LL d; int id; int operator<(const node &x)const { return d>x.d; } node(int id=0,LL d=0):id(id),d(d){} }; LL d[N]; priority_queue<node>Q; int vis[N]; inline int cmp1(const point &a,const point &b){ return a.x<b.x; } inline int cmp2(const point &a,const point &b){ return a.y<b.y; } inline void connect(int x,int y,int d){ to[++cnt]=y; next[cnt]=start[x]; start[x]=cnt; len[cnt]=d; } int n; int main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif n=read(); for (int i=1;i<=n;i++){ a[i].x=read(); a[i].y=read(); a[i].pos=i; } sort(a+1,a+n+1,cmp1); for (int i=1;i<n;i++){ connect(a[i].pos,a[i+1].pos,a[i+1].x-a[i].x); connect(a[i+1].pos,a[i].pos,a[i+1].x-a[i].x); } sort(a+1,a+n+1,cmp2); for (int i=1;i<n;i++){ connect(a[i].pos,a[i+1].pos,a[i+1].y-a[i].y); connect(a[i+1].pos,a[i].pos,a[i+1].y-a[i].y); } for (int i=2;i<=n;i++) d[i]=inf; Q.push(node(1,0)); while (!Q.empty()){ while (Q.size() && vis[Q.top().id]) Q.pop(); if (Q.empty()) break; int x=Q.top().id; Q.pop(); vis[x]=1; for (int p=start[x];p;p=next[p]){ if (d[to[p]]>d[x]+len[p]){ d[to[p]]=d[x]+len[p]; Q.push(node(to[p],d[to[p]])); } } if (vis[n]) break; } printf("%lld\n",d[n]); return 0; }