BZOJ-4152: [AMPPZ2014]The Captain

[文章目录]

Description

给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。2<=n<=200000 ,0<=x[i],y[i]<=10^9

两个节点的费用只有两种情况:x的差或y的差。
那么按照一维排序,将所有相邻两个点连边即等价于任意两点连边,距离为该维的差。
这样边数就降到2n了,最短路即可。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000 
int n;
struct node
{
    int x,y,id;
}a[N];
bool cmpx(node x,node y){return x.x<y.x;}
bool cmpy(node x,node y){return x.y<y.y;}
int Abs(int x){return x>0?x:-x;}
int Dis(node x,node y){return min(Abs(x.x-y.x),Abs(x.y-y.y));}
int head[N],to[N<<2],nxt[N<<2],f[N<<2],cnt;
inline void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
struct dij
{
    int x,dis;
    dij(){}
    dij(int _x,int _dis):x(_x),dis(_dis){}
};
bool operator < (dij x,dij y){return x.dis>y.dis;}
priority_queue<dij>q;
int dis[N];
int dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0; q.push(dij(1,0)); int x,y,i;
    while(!q.empty())
    {
        x=q.top().x; y=q.top().dis; q.pop();
        if(y>dis[x]) continue;
        for(i=head[x];i;i=nxt[i])
            if(y+f[i]<dis[to[i]])
            {
                dis[to[i]]=y+f[i];
                q.push(dij(to[i],y+f[i]));
            }
    }
    return dis[n];
}
int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;++i) a[i].id=i,scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmpx);
    for(i=1;i<n;++i) add(a[i].id,a[i+1].id,Dis(a[i],a[i+1]));
    sort(a+1,a+n+1,cmpy);
    for(i=1;i<n;++i) add(a[i].id,a[i+1].id,Dis(a[i],a[i+1]));
    printf("%d\n",dijkstra());
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注