BZOJ4152 AMPPZ2014 The Captain
Description
给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。
Input
第一行包含一个正整数n(2<=n<=200000)，表示点数。
接下来n行，每行包含两个整数x[i],yi，依次表示每个点的坐标。
Output
一个整数，即最小费用。
Sample Input
5
2 2
1 1
4 5
7 1
6 7
Sample Output
2
一开始想到了分别按X和Y排序，把相邻的点建边
结果后来RE了，因为有可能有很多个点的纵坐标或者横坐标相等，这样判断很不优秀
然后想一想有哪些边是可以减掉不要的
如果按照X排序的时候y值的差还要比x小，那么这条边显然是没有意义或者可以被代替掉的，所以每次我们加边就判断一下x和y的差，然后贪心加边，边数还是O(n)的
然后就做完了
#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define pi pair<int,int>
#define mp make_pair
#define LL long long
struct Node{int x,y,id;}p[N];
struct Edge{int v,w,next;}E[N<<3];
int n,tot=0,head[N];
LL d[N];
bool cmpx(Node a,Node b){return a.x<b.x;}
bool cmpy(Node a,Node b){return a.y<b.y;}
void add(int u,int v,int w){
E[++tot]=(Edge){v,w,head[u]};head[u]=tot;
E[++tot]=(Edge){u,w,head[v]};head[v]=tot;
}
void Dijk(){
priority_queue<pi,vector<pi>,greater<pi> > q;
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push(mp(0,1));
while(!q.empty()){
int u=q.top().second;q.pop();
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(d[v]>d[u]+E[i].w){
d[v]=d[u]+E[i].w;
q.push(mp(d[v],v));
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
sort(p+1,p+n+1,cmpx);
for(int i=1;i<n;i++)
if(p[i+1].x-p[i].x<=abs(p[i+1].y-p[i].y))add(p[i].id,p[i+1].id,p[i+1].x-p[i].x);
sort(p+1,p+n+1,cmpy);
for(int i=1;i<n;i++)
if(p[i+1].y-p[i].y<=abs(p[i+1].x-p[i].x))add(p[i].id,p[i+1].id,p[i+1].y-p[i].y);
Dijk();
printf("%lld",d[n]);
return 0;
}