51nod 3010 The Captain

暴力构图为 \(O(n^2)\) 无法实现，但可以发现有些边无用，可以先按 x 排序，第 i 号点与第 i+1 号点一定最近，所以建一条边，y 坐标同理，然后跑最短路即可自动选择 \(min(|x_1-x_2|,|y_1-y_2|)\)

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f;
const int N=1e6+2;

struct edge{
	int to;
	long long w;
};
vector<edge> v[N];

int n,m;
long long dis[N];
bool done[N];
int s,t;
struct ss{
	int x,y,id;
}a[N];

bool cmp1(ss g,ss h){
	return g.x<h.x;
}
bool cmp2(ss g,ss h){
	return g.y<h.y;
}

void spfa(){
	for(int i=1;i<=n;i++){
		dis[i]=INF,done[i]=0;
	}
	
	dis[s]=0;
	queue<int> q;
	q.push(s);
	
	while(!q.empty()){
		int u=q.front();
		
		q.pop();
		done[u]=0;
		
		for(int i=0;i<v[u].size();i++){
			edge y=v[u][i];
			
			if(dis[y.to]>y.w+dis[u]){
				dis[y.to]=y.w+dis[u];
				if(!done[y.to]){
					q.push(y.to);
					done[y.to]=1;
				}
			}
		}
	}
	cout<<dis[t];
}
                                
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		a[i].id=i;
	}
	
	sort(a+1,a+n+1,cmp1);
	
	for(int i=1;i<n;i++){
		v[a[i].id].push_back({a[i+1].id,a[i+1].x-a[i].x});
		v[a[i+1].id].push_back({a[i].id,a[i+1].x-a[i].x});
	}
	sort(a+1,a+n+1,cmp2);
	
	for(int i=1;i<n;i++){
		v[a[i].id].push_back({a[i+1].id,a[i+1].y-a[i].y});
		v[a[i+1].id].push_back({a[i].id,a[i+1].y-a[i].y});
	}

	s=1,t=n;

	spfa();

	return 0;
}