bzoj 4152: [AMPPZ2014]The Captain

题目大意：在坐标轴上有n个点，一个点(x1,y1)到另一个点(x2,y2)的距离为min(|x2-x1，|y2-y1|)，求解从1点出发到n点的最短路径。
n<=20000；
题解：
这道题是真的好题虽然我单凭自己不会做 。
首先考虑题意，这里权值是最小值，那么可以经过思考，得到一个性质：对于三个点：A(x1,y1)、B(x2,y2)、C(x3,y3),令B在A、C中间（即B的x、y项都在中间），定义dis(A,B)_x=a,dis(C,B)_y=b,dis(C,B)_x=c,dis(A,B)_y=d，那么一定有：min(a,c)+min(b,d)<=min(a+c,b+d)即使对于A、B、C三点，经过B点有可能使得从A到C权值缩小。（因为这个性质，这道题才有意义。）题目的要求就是通过经过中间点减少从1到n点的权值。
显然有一种做法，就是：将所有点两两之间连接，然后最短路，这样一定有正确答案，但是200000的平方，呵呵。同样显然的是这样连边有很大一部分是存在浪费的，即如果有一边两端的两点中间有一点，那么这一边就没有意义，很明显可以由中间一点连出的两条边代替并且可能更优。综上所述，只有两点之间没有其他点的连边有意义，不存在浪费。这样贪心思路就和明显了，这样贪心一定是最优的。证明完毕。
由于一个点可能存在多个连边不经过其他点，这个直接讨论是平方级的，直接维护很难做到。根据定义中间的方式，可以顺利想到一种做法，分别由x、y讨论，先按照x排序后连边，然后按照y排序后连边，这样因为x,y分别连边的时候具有单调性，所以所连的边之间都在x或y方面符合贪心策略的连边（由于贪心策略，如果越过一点进行连边，那么中间点要么可以被代替，除了被代替，剩下可能产生更优的解得情况会在另一个方向上讨论到），由于所有边都已经是单方面符合贪心策略的边，同时连向其他点的边不符合贪心策略，在不漏方面也能证明。但是由于只是满足了x或y的贪心策略，有可能存在不满足完全贪心策略的边，这样会增加一部分无用边，但是这样讨论无疑是最简便的。
连边方法的正确性得证。
由于满足贪心策略的连接方法有多种（上面已经论证：一个点可能存在多个连边不经过其他点），同时还有存在废边，所以最后需要跑最短路来求得最小权值，最终证明完毕。
P.S.这道题真的是好题，如果直接在外面搜到题解后按照题解的做法做就真的把题目浪费了，算法过程很简单，但是贪心的思路很重要，值得仔细研究。
P.S.我不得不吐槽下外面搜到的题解，只有解法让我自己写证明写了1个小时，不过能把这个理顺我还是很开心的。
P.S。可能是数据专门卡你或是这种统计方法存在不少重边和环的缘故，spfa会被卡t，最短路请写dij。
最后附上还没写这篇证明用时间多的一份代码：
靠上来缩进不明显了，但是其实不重要，代码也没有啥，都是板子，就是要注意一下链式前向星需要开8*1e5就好了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5*2+10;
inline int read()
{
 int ret=0;char c=getchar();
 while(c>'9'||c<'0') c=getchar();
 while(c>='0'&&c<='9')
  ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
 return ret;
}
struct Point{
 int x,y,id;
}p[maxn];
struct Edge{
 int to,nxt,val;
}e[maxn*4];
struct dijk{
 int to,val;
 dijk(int _to,int _val):to(_to),val(_val){}
 const bool operator < (const dijk a)const {return val>a.val;} 
};
priority_queue<dijk>q;
inline bool cmp(Point a,Point b){return a.x<b.x;}
inline bool cmpe(Point a,Point b){return a.y<b.y;}
int n,head[maxn],cnt,dis[maxn]; 
bool vis[maxn];
inline void add(int x,int y,int z)
{
 cnt++;e[cnt].to=y,e[cnt].val=z;
 e[cnt].nxt=head[x],head[x]=cnt;
}
void dij()
{
 memset(dis,0x7f,sizeof(dis)),dis[1]=0;
 q.push(dijk(1,0));
 while(!q.empty()){
  dijk now=q.top();q.pop();
  vis[now.to]=true;
  for(int i=head[now.to];i;i=e[i].nxt){
   int to=e[i].to,val=e[i].val;
   if(dis[now.to]+val<dis[to]&&!vis[to]){
    dis[to]=dis[now.to]+val;
    q.push(dijk(to,dis[to]));
   }
  }	
 }
}
int main()
{
 freopen("bzoj1452.in","r",stdin);
 n=read();
 for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(),p[i].id=i;
 sort(p+1,p+1+n,cmp);
 for(int i=1;i<n;i++){
  int val=p[i+1].x-p[i].x;
  add(p[i].id,p[i+1].id,val);add(p[i+1].id,p[i].id,val);
 }
 sort(p+1,p+1+n,cmpe);
 for(int i=1;i<n;i++){
  int val=p[i+1].y-p[i].y;
  add(p[i].id,p[i+1].id,val);add(p[i+1].id,p[i].id,val);
 }
 dij();
 printf("%d",dis[n]);
 return 0;
}