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 又一道卡spfa的最短路题，学长HugeGun说用堆优dijkstra就好，但是我只会spfa，然后狂T，又以为有什么智障错误内心紧张无比。分别根据横坐标和纵坐标排两次序，把每次排好序后相邻的连边（似乎以前有学长讲过？）。最近连续遇到两道卡spfa的题了，或许真的应该学一学堆优dijkstra。用SLF优化的spfa刚好卡过的代码：
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=2e5+10,maxm=4e5+10;
int n;int aa;char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}struct Node1{
int pos,x;
}node1[maxn];struct Node2{
int pos,x;
}node2[maxn];bool cmp1(const Node1& a,const Node1& b) {
return a.x<b.x;
}bool cmp2(const Node2& a,const Node2& b) {
return a.x<b.x;
}int fir[maxn],nxt[2*maxm],to[2*maxm],v[2*maxm],e=0;
void add(int x,int y,int z) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z;
to[++e]=x;nxt[e]=fir[y];fir[y]=e;v[e]=z;
}int dis[maxn],zz[maxn];
bool vis[maxn];
void spfa() {
for(int i=2;i<=n;++i) dis[i]=0x3f3f3f3f;
int s=1,t=0,x,y,z,tot=1;
dis[1]=0;zz[++t]=1;vis[1]=1;
while(tot) {
x=zz[s];s=(s+1)%maxn;vis[x]=0;tot--;
for(y=fir[x];y;y=nxt[y]) {
z=to[y];
if(dis[z]<=dis[x]+v[y]) continue;
dis[z]=dis[x]+v[y];
if(!vis[z]) {
vis[z]=1;tot++;
if(dis[z]<=dis[zz[s]]) {
s=(s-1+maxn)%maxn;
zz[s]=z;
}
else {
t=(t+1)%maxn;
zz[t]=z;
}
}
}
}
printf("%d",dis[n]);
}int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
node1[i].pos=node2[i].pos=i;
scanf("%d%d",&node1[i].x,&node2[i].x);
}
sort(node1+1,node1+n+1,cmp1);
for(int i=1;i<n;++i) add(node1[i].pos,node1[i+1].pos,node1[i+1].x-node1[i].x);
sort(node2+1,node2+n+1,cmp2);
for(int i=1;i<n;++i) add(node2[i].pos,node2[i+1].pos,node2[i+1].x-node2[i].x);
spfa();
return 0;
}
