davidwang's Blog

首先按照x,y分别排序相邻的连边然后跑最短路，这个应该是显然的，不知道用了什么卡SPFA的方法，必须用堆+Dij

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <deque>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 200010;
const LL inf = 1LL<<60;
struct point{
	int x,y,pos;
}a[N];
int start[N],next[N<<2],to[N<<2],len[N<<2],cnt;
struct node{
	LL d;
	int id;
	int operator<(const node &x)const {
		return d>x.d;
	}
	node(int id=0,LL d=0):id(id),d(d){}
};
LL d[N];
priority_queue<node>Q;
int vis[N];
inline int cmp1(const point &a,const point &b){
	return a.x<b.x;
}
inline int cmp2(const point &a,const point &b){
	return a.y<b.y;
}
inline void connect(int x,int y,int d){
	to[++cnt]=y; next[cnt]=start[x];
	start[x]=cnt; len[cnt]=d;
}
int n;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	for (int i=1;i<=n;i++){
		a[i].x=read();
		a[i].y=read();
		a[i].pos=i;
	}
	sort(a+1,a+n+1,cmp1);
	for (int i=1;i<n;i++){
		connect(a[i].pos,a[i+1].pos,a[i+1].x-a[i].x);
		connect(a[i+1].pos,a[i].pos,a[i+1].x-a[i].x);
	}
	sort(a+1,a+n+1,cmp2);
	for (int i=1;i<n;i++){
		connect(a[i].pos,a[i+1].pos,a[i+1].y-a[i].y);
		connect(a[i+1].pos,a[i].pos,a[i+1].y-a[i].y);
	}
	for (int i=2;i<=n;i++) d[i]=inf;
	Q.push(node(1,0));
	while (!Q.empty()){
		while (Q.size() && vis[Q.top().id]) Q.pop();
		if (Q.empty()) break;
		int x=Q.top().id; Q.pop();
		vis[x]=1;
		for (int p=start[x];p;p=next[p]){
			if (d[to[p]]>d[x]+len[p]){
				d[to[p]]=d[x]+len[p];
				Q.push(node(to[p],d[to[p]]));
			}
		}
		if (vis[n]) break;
	}
	printf("%lld\n",d[n]);
	return 0;
}