BZOJ4152 AMPPZ2014 The Captain（最短路）

　　事实上每次走到横坐标或纵坐标最接近的点一定可以取得最优方案。于是这样连边跑最短路就可以了。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
#define N 200010
int n,p[N],d[N],t=0;
bool flag[N];
struct point{int x,y,i;
}a[N];
struct data{int to,nxt,len;
}edge[N<<2];
struct data2
{int x,d;bool operator <(const data2&a) const{return d>a.d;}
};
priority_queue<data2> q;
void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
void dijkstra()
{while (!q.empty()) q.pop();for (int i=2;i<=n;i++) d[i]=1000000001;q.push((data2){1,0});memset(flag,0,sizeof(flag));for (int i=1;i<=n;i++){while (!q.empty()&&flag[q.top().x]) q.pop();if (q.empty()) break;data2 v=q.top();q.pop();flag[v.x]=1;for (int j=p[v.x];j;j=edge[j].nxt)if (v.d+edge[j].len<d[edge[j].to]){d[edge[j].to]=v.d+edge[j].len;q.push((data2){edge[j].to,d[edge[j].to]});}}
}
bool cmp1(const point&a,const point&b)
{return a.x<b.x;
}
bool cmp2(const point&a,const point&b)
{return a.y<b.y;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("bzoj4152.in","r",stdin);freopen("bzoj4152.out","w",stdout);const char LL[]="%I64d\n";
#elseconst char LL[]="%lld\n";
#endifn=read();for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].i=i;sort(a+1,a+n+1,cmp1);for (int i=1;i<n;i++)addedge(a[i].i,a[i+1].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y))),addedge(a[i+1].i,a[i].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y)));sort(a+1,a+n+1,cmp2);for (int i=1;i<n;i++)addedge(a[i].i,a[i+1].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y))),addedge(a[i+1].i,a[i].i,min(abs(a[i].x-a[i+1].x),abs(a[i].y-a[i+1].y)));dijkstra();cout<<d[n];return 0;
}

 

转载于:https://www.cnblogs.com/Gloid/p/9827815.html

总结

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

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