问题描述
给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。
输入格式
第一行包含一个正整数n(2<=n<=200000)，表示点数。
接下来n行，每行包含两个整数x[i],y[i] (0<=x[i],y[i]<=10^9)，依次表示每个点的坐标。
输出格式
一个整数，即最小费用。
样例输入
5
2 2
1 1
4 5
7 1
6 7
样例输出
2
解析
首先想到的应该是(n^2)连边，但显然不可行。接下来的任务就是尽量减少边的数量。可以发现，若以两点作为左上、右下角的矩形内有一点，那么两点之间的最短路一定是经过这个点的。所以，我们只需要依次按x和y坐标排序后连接相邻的两点，跑最短路即可。
注意此题卡SPFA。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 200002
#define M 400002
using namespace std;
struct point{
int x,y,id;
}a[N];
int head[N],ver[M*2],nxt[M*2],edge[M*2],l;
int n,i,dis[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void insert(int x,int y,int z)
{
l++;
ver[l]=y;
edge[l]=z;
nxt[l]=head[x];
head[x]=l;
}
int cmp1(const point &a,const point &b)
{
return a.x<b.x;
}
int cmp2(const point &a,const point &b)
{
return a.y<b.y;
}
void Dijkstra()
{
priority_queue<pair<int,int> > q;
memset(dis,0x3f,sizeof(dis));
q.push(make_pair(0,1));
dis[1]=0;
while(!q.empty()){
int x=q.top().second,d=-q.top().first;
q.pop();
if(dis[x]!=d) continue;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(dis[y]>d+edge[i]){
dis[y]=d+edge[i];
q.push(make_pair(-dis[y],y));
}
}
}
}
int main()
{
n=read();
for(i=1;i<=n;i++){
a[i].x=read(),a[i].y=read();
a[i].id=i;
}
sort(a+1,a+n+1,cmp1);
for(i=2;i<=n;i++){
insert(a[i].id,a[i-1].id,a[i].x-a[i-1].x);
insert(a[i-1].id,a[i].id,a[i].x-a[i-1].x);
}
sort(a+1,a+n+1,cmp2);
for(i=2;i<=n;i++){
insert(a[i].id,a[i-1].id,a[i].y-a[i-1].y);
insert(a[i-1].id,a[i].id,a[i].y-a[i-1].y);
}
Dijkstra();
cout<<dis[n]<<endl;
return 0;
}