最短路

　　题解：

　　按x坐标排序，相邻点之间连边。满足dist(x1,x3)<=dist(x1,x2)+dist(x2,x3)（因为可以走y）

　　再按y坐标排序，相邻点之间连边。同上

　　然而SPFA挂了……写了Dijkstra

1 /************************************************************** 2     Problem: 4152 3     User: Tunix 4     Language: C++ 5     Result: Accepted 6     Time:4304 ms 7     Memory:27204 kb 8 ****************************************************************/ 9  10 //BZOJ 415211 #include
      
       12 #include
       
        13 #include
        
         14 #include
         
          15 #include
          
           16 #include
           
            17 #include
            
             18 #define rep(i,n) for(int i=0;i
             
              =n;--i)21 using namespace std;22 typedef long long LL;23 inline int getint(){24 int r=1,v=0; char ch=getchar();25 for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1;26 for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch;27 return r*v;28 }29 const int N=2e5+10,INF=~0u>>1;30 /*******************template********************/31 32 int head[N],to[N<<3],nxt[N<<3],l[N<<3],cnt;33 void add(int x,int y,int z){34 to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; l[cnt]=z;35 to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; l[cnt]=z;36 }37 int n,d[N];38 struct node{39 int x,y,num;40 }a[N];41 bool cmpx(node a,node b){ return a.x
              
                pii;44 #define mp make_pair45 #define se second46 priority_queue
               
                
                 ,greater
                 
                   >Q;47 bool vis[N];48 int main(){49 #ifndef ONLINE_JUDGE50 freopen("4152.in","r",stdin);51 freopen("4152.out","w",stdout);52 #endif 53 n=getint();54 F(i,1,n) a[i].x=getint(),a[i].y=getint(),a[i].num=i;55 sort(a+1,a+n+1,cmpx);56 F(i,1,n-1) add(a[i].num,a[i+1].num,a[i+1].x-a[i].x);57 sort(a+1,a+n+1,cmpy);58 F(i,1,n-1) add(a[i].num,a[i+1].num,a[i+1].y-a[i].y);59 60 F(i,2,n) d[i]=INF;61 d[1]=0;62 Q.push(mp(0,1));63 while(!Q.empty()){64 int x=Q.top().se; Q.pop();65 if (vis[x]) continue;66 vis[x]=1;67 for(int i=head[x];i;i=nxt[i])68 if (d[to[i]]>d[x]+l[i]){69 d[to[i]]=d[x]+l[i];70 Q.push(mp(d[to[i]],to[i]));71 }72 }73 printf("%d\n",d[n]);74 return 0;75 }