4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec  Memory Limit: 256 MB

Submit: 1517  Solved: 603

[][][]

Description

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

 

Input

第一行包含一个正整数n(2<=n<=200000)，表示点数。

接下来n行，每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9)，依次表示每个点的坐标。

 

 

 

Output

一个整数，即最小费用。

 

Sample Input

5

2 2

1 1

4 5

7 1

6 7

Sample Output

2

HINT

 

Source

 

按横坐标排序，相邻点建边

按纵坐标排序，相邻点建边

dijkstra可过

1 #include
     
       2 #define ll long long 3 #define mp make_pair 4 #define N 200005 5 using namespace std; 6 typedef pair
      
       pii; 7 int n,tot,vis[N],hd[N],d[N]; 8 struct P{
   int x,y,id;}a[N]; 9 struct edge{
   int v,w,next;}e[N*10];10 bool cmp1(P a,P b){
   return a.x
       
        ,greater
        
          >q;20 void dijkstra(){21     for(int i=1;i<=n;i++)d[i]=1<<30;22     d[1]=0;q.push(mp(0,1));23     while(!q.empty()){24         pii x=q.top();q.pop();25         int u=x.second;26         if(vis[u])continue;vis[u]=1;27         for(int i=hd[u];i;i=e[i].next){28             int v=e[i].v;29             if(vis[v])continue;30             if(d[v]>d[u]+e[i].w){31                 d[v]=d[u]+e[i].w;32                 q.push(mp(d[v],v));33             }34         }35     }36 }37 38 int main(){39     scanf("%d",&n);40     for(int i=1;i<=n;a[i].id=i,i++)41     scanf("%d%d",&a[i].x,&a[i].y);42     sort(a+1,a+1+n,cmp1);    43     for(int i=1;i