4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec   Memory Limit: 256 MB
Submit: 704   Solved: 269
[ Submit][ Status][ Discuss]

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


题意：给你n个点的坐标，每两个点之间的花费是 min(|x1-x2|,|y1-y2|),求从第一个点到第n个点的最小花费。


题目思路：  这题的关键在于怎么建图，，只要建好了图直接跑最短路，，在网上借鉴的其他大牛的方法，只需分别按x和y排下序，然后用邻接表建图，这里开始没理解为什么要这么做，最后在纸上画了画就发现了，，因为排好序后的点的最短的点为相邻的两个点，所以只需按x找最短得和按y找最短的，最后在跑最短路，有人说这里卡spfa，，我也没试过，，我用的是dij+优先队列优化的，，跑了五秒，


AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int maxn = 2e5+100;
const int Inf = 0x7fffffff;
int n,e;

int hed[maxn<<1],dis[maxn];

struct P{
    int x,y,id;
}Poin[maxn];

struct L{
    int u,v,w,nex;
}Lin[maxn<<2];

struct Nod{
    int x,dis;
    bool operator < (const Nod &a)const{
      return a.dis<dis;
    }
};

bool cmp1(P a,P b){return a.x<b.x;}

bool cmp2(P a, P b){return a.y<b.y;}

void addedge(int u,int v,int w){
    Lin[e].u=u,Lin[e].v=v,Lin[e].w=w,Lin[e].nex =hed[u],hed[u]=e++;
    Lin[e].u=v,Lin[e].v=u,Lin[e].w=w,Lin[e].nex =hed[v],hed[v]=e++;
}

void Dij(){
    for(int i=1;i<=n;i++)
        dis[i]=Inf;
    dis[1]=0;
    Nod a={1,0};
    priority_queue<Nod>q;
    q.push(a);
    while(!q.empty()){
        a=q.top();
        q.pop();
        int now = a.x;
        for(int i=hed[now];~i;i=Lin[i].nex){
             Nod b;
             int v=Lin[i].v;
             if(dis[v]>dis[now]+Lin[i].w){
                dis[v]=dis[now]+Lin[i].w;
                b.x=v;
                b.dis=dis[v];
                q.push(b);
             }
        }
    }
}
int main()
{
   cin>>n;
   e=0;
   memset(hed,-1,sizeof(hed));
   for(int i=0;i<n;i++){
    scanf("%d%d",&Poin[i].x,&Poin[i].y);
    Poin[i].id=i+1;
   }
   sort(Poin,Poin+n,cmp1);
   for(int i=0;i<n-1;i++)
      addedge(Poin[i].id,Poin[i+1].id,Poin[i+1].x-Poin[i].x);
   sort(Poin,Poin+n,cmp2);
   for(int i=0;i<n-1;i++)
      addedge(Poin[i].id,Poin[i+1].id,Poin[i+1].y-Poin[i].y);
   Dij();
   cout<<dis[n]<<endl;
   return 0;
}