[文章目录]
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;
}