BZOJ 4152

直接写一个队列会WA！！！（WA了好几次）
所以改用优先队列，一遍过掉。

这个题思路挺简单的:
        虽然说是要|x1-x2|和|y1-y2|的最小值，但是没什么意义，不如直接建两条边权值分别为|x1-x2|和|y1-y2|，然后跑一遍Dij！由于你要到达的是点n，那么建边只需要从左往右排序后顺次建边，再从下到上排序顺次建边，跑最短路就好了！

（注意，为了防止一个点多次进入队列造成时间浪费，应该用一个标记避免这种情况发生，这里我用了exp）

&&我可能会防止你们复制代码。

#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define why pair<long long,int>
using namespace std;

const int M=2e5+10;
int n,vis[M];
long long dis[M];
bool exp[M];
struct node{
	int x,y,id;
}p[M];
int cnt,head[M<<2];
struct edge{
	int to,nxt;
	long long w;
}e[M<<2];
priority_queue< why,vector<why>,greater<why> > Q;

inline void Add(int x,int y,int z){
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	e[cnt].w=z;
	head[x]=cnt;
}

inline bool CMP1(node a,node b){
	return a.x<b.x;
}

inline bool CMP2(node a,node b){
	return a.y<b.y;
}

void Dij(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	Q.push(make_pair(0,1));
	dis[1]=0;
	while(!Q.empty()){
		int u=Q.top().second;
		Q.pop();
		if(exp[u]) continue;
		exp[u]=true;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		p[i].x=x,p[i].y=y,p[i].id=i;
	}
	sort(p+1,p+n+1,CMP1);
	for(int i=1;i<n;i++)
		Add(p[i].id,p[i+1].id,p[i+1].x-p[i].x),Add(p[i+1].id,p[i].id,p[i+1].x-p[i].x);
	sort(p+1,p+n+1,CMP2);
	for(int i=1;i<n;i++)
		Add(p[i].id,p[i+1].id,p[i+1].y-p[i].y),Add(p[i+1].id,p[i].id,p[i+1].y-p[i].y);
	Dij();
	printf("%lld\n",dis[n]);
	return 0;
}