本文共 1283 字，大约阅读时间需要 4 分钟。

这题的话大概就是一个最短路。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define swap(x,y) {int tt=x;x=y;y=tt;}#define inf 0x3f3f3f3f using namespace std;const int N=200005;int n;struct qq{  int x,y,id;}s[N];bool cmp (qq a,qq b){  return a.x
        
         ,vector
         
          
            >,greater
           
            
              > > q;void SPFA (){ for (int u=1;u<=n;u++) f[u]=inf; memset(in,false,sizeof(in)); in[1]=true; q.push(make_pair(0,1)); f[1]=0; while (!q.empty()) { int x=q.top().second;q.pop(); for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; if (f[y]>f[x]+e[u].z) { f[y]=f[x]+e[u].z; if (in[y]==false) { in[y]=true; q.push(make_pair(f[y],y)); } } } in[x]=false; } printf("%d\n",f[n]);}int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} return x;}int main(){ num=0;memset(last,-1,sizeof(last)); n=read(); for (int u=1;u<=n;u++) { s[u].x=read();s[u].y=read(); s[u].id=u; } sort(s+1,s+1+n,cmp); for (int u=2;u<=n;u++) init(s[u].id,s[u-1].id,s[u].x-s[u-1].x); sort(s+1,s+1+n,cmp1); for (int u=2;u<=n;u++) init(s[u].id,s[u-1].id,s[u].y-s[u-1].y); SPFA(); return 0;}