【bzoj4152: [AMPPZ2014]The Captain】最短路

4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 1459  Solved: 576
[Submit][Status][Discuss]

Description

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

Input

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

Output

一个整数，即最小费用。

Sample Input

5
2 2
1 1
4 5
7 1
6 7

Sample Output

2

HINT

Source

鸣谢Claris上传

刚开始想着贪心，把边按x和y分别排序，然后对于每个xi向后连6个（这里是贪心，因为如果是暴力的话把所有的边都建出来，而我只是把相对较优的几条边建出来了）。然后跑最短路，这里跑spfa会挂，要跑dijkstra+堆优化。然后就过了。

后来仔细一想，发现正解就是我最贪心的情况：每个xi只向后连一个就好了，因为单单对于x来说，(x1,x3)=(x1,x2)+(x2,x3) (这里的x是排好序的，所以成立)，所以对于min(|x1-x2|,|y1-y2|)是|x1-x2|，即是用x的差的绝对值来更新的话，我们用上述建边方法就是最优的，同理可以用同样的方法对y建边。

所以分别按x和y排序，相邻的点连边，跑最短路就Ok了

#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<vector> #include<algorithm> #define Pa pair<int,int> #define N 200005 #define M (N*50*2) #define INF 1e9+7 using namespace std; int k,fir[N],x[N],y[N],dis[N],n,vis[N]; struct ha{int d,p; }a[N],b[N]; struct he{int r,c,nx; }A[M]; int abs(int x){if(x<0) return -x;return x; } bool cmp(ha a,ha b){return a.d<b.d; } void add(int l,int r,int c){k++;A[k].r=r;A[k].c=c;A[k].nx=fir[l];fir[l]=k; } /*queue<int>Q; int spfa(){for(int i=1;i<=n;i++)dis[i]=INF;dis[1]=0;Q.push(1);while(!Q.empty()){int u=Q.front();Q.pop();vis[u]=0;for(int i=fir[u];i!=-1;i=A[i].nx)if(dis[u]+A[i].c<dis[A[i].r]){dis[A[i].r]=dis[u]+A[i].c;if(!vis[A[i].r]){vis[A[i].r]=1;Q.push(A[i].r);}}}return dis[n]; }*/ int dij(int st,int ed){priority_queue<Pa,vector<Pa>,greater<Pa> >Q;for(int i=st;i<=ed;i++) dis[i]=INF; Q.push(make_pair(0,st));dis[st]=0;while(!Q.empty()){int u=Q.top().second;int Dis=Q.top().first;Q.pop();if(Dis>dis[u]) continue;for(int i=fir[u];i!=-1;i=A[i].nx)if(dis[u]+A[i].c<dis[A[i].r])dis[A[i].r]=dis[u]+A[i].c,Q.push(make_pair(dis[A[i].r],A[i].r));}return dis[ed]; } int main(){freopen("1.in","r",stdin);memset(fir,-1,sizeof(fir));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&x[i],&y[i]);a[i].d=x[i],a[i].p=i;b[i].d=y[i],b[i].p=i;}sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp);for(int i=1;i<n;i++)for(int j=i+1;j<=i+1;j++)add(a[i].p,a[j].p,a[j].d-a[i].d),add(a[j].p,a[i].p,a[j].d-a[i].d);for(int i=1;i<n;i++)for(int j=i+1;j<=i+1;j++)add(b[i].p,b[j].p,b[j].d-b[i].d),add(b[j].p,b[i].p,b[j].d-b[i].d); // printf("%d\n",spfa());printf("%d\n",dij(1,n)); }

总结

以上是生活随笔为你收集整理的【bzoj4152: [AMPPZ2014]The Captain】最短路的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。