[bzoj4152][最短路][Dijkstra]The Captain

本文主要是介绍[bzoj4152][最短路][Dijkstra]The Captain，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

Input

第一行包含一个正整数n(2<=n<=200000)，表示点数。
接下来n行，每行包含两个整数x[i],yi，依次表示每个点的坐标。

Output

一个整数，即最小费用。

Sample Input

5

2 2

1 1

4 5

7 1

6 7

Sample Output

2

题解

如果考虑每个点对都连边的话，复杂度N^2
我们看看怎么优化这个建图
把点按x排序，两个点之间只看x的距离，实际上就相当于这两个点中间找一个中间点，这两个点分别到这个中间点的距离和
那么这个操作是可继续拆分的，于是我们把x排序后，相邻两点连边即可
y坐标讨论相同
最后跑Dijkstra即可

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct node
{int x,y,c,next;
}a[810000];int len,last[210000];
void ins(int x,int y,int c)
{len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
}
struct ct{int x,y,op;}P[210000];
bool cmp1(ct n1,ct n2){return n1.x<n2.x;}
bool cmp2(ct n1,ct n2){return n1.y<n2.y;}
int d[210000];
struct pt
{int x;friend bool operator <(pt n1,pt n2){return d[n1.x]>d[n2.x];}
};
priority_queue<pt> q;
bool v[210000];
int n;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&P[i].x,&P[i].y),P[i].op=i;sort(P+1,P+1+n,cmp1);for(int i=1;i<n;i++)ins(P[i].op,P[i+1].op,P[i+1].x-P[i].x),ins(P[i+1].op,P[i].op,P[i+1].x-P[i].x);sort(P+1,P+1+n,cmp2);for(int i=1;i<n;i++)ins(P[i].op,P[i+1].op,P[i+1].y-P[i].y),ins(P[i+1].op,P[i].op,P[i+1].y-P[i].y);memset(d,63,sizeof(d));d[1]=0;memset(v,false,sizeof(v));v[1]=true;pt tmp;tmp.x=1;q.push(tmp);while(!q.empty()){tmp=q.top();int x=tmp.x;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(d[y]>d[x]+a[k].c){d[y]=d[x]+a[k].c;if(v[y]==false){v[y]=true;pt cnt;cnt.x=y;q.push(cnt);}}}q.pop();v[x]=false;}printf("%d\n",d[n]);return 0;
}