BZOJ-4152-最短路

我不是女神ヾ 2022-07-16 03:52 69阅读 0赞

## 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 ##

题意：给你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;
    }

[Submit]: http://www.lydsy.com/JudgeOnline/submitpage.php?id=4152
[Status]: http://www.lydsy.com/JudgeOnline/problemstatus.php?id=4152
[Discuss]: http://www.lydsy.com/JudgeOnline/bbs.php?id=4152