给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。
BZOJ4152: [AMPPZ2014]The Captain
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #define MAXN 200010 #define MAX (1LL<<61) using namespace std; int n,s,t,c=1; int head[MAXN]; long long path[MAXN]; bool vis[MAXN]; struct Point{ int x,y,id; }point[MAXN]; struct Edge{ int next,to; long long w; }a[MAXN<<2]; struct node{ int x,dis; bool operator <(const node &p)const{ return dis>p.dis; } }; priority_queue<node> q; inline int read(){ int date=0,w=1;char c=0; while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();} return date*w; } inline bool cmp1(const Point &p,const Point &q){ return p.x<q.x; } inline bool cmp2(const Point &p,const Point &q){ return p.y<q.y; } inline int relax(int u,int v,long long w){ if(path[v]>path[u]+w){ path[v]=path[u]+w; return 1; } return 0; } inline void add(int u,int v,int w){ a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++; a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++; } void dijkstra(){ node u,v; for(int i=1;i<=n;i++){path[i]=MAX;vis[i]=false;} u.x=s;u.dis=path[s]=0; q.push(u); while(!q.empty()){ u=q.top(); q.pop(); if(!vis[u.x]){ vis[u.x]=true; for(int i=head[u.x];i;i=a[i].next){ v.x=a[i].to; if(!vis[v.x]){ path[v.x]=min(path[v.x],path[u.x]+a[i].w); v.dis=u.dis+a[i].w; q.push(v); } } } } } void work(){ dijkstra(); printf("%lld\n",path[t]); } void init(){ n=read(); s=1;t=n; for(int i=1;i<=n;i++){ point[i].x=read();point[i].y=read(); point[i].id=i; } sort(point+1,point+n+1,cmp1); for(int i=1;i<n;i++)add(point[i].id,point[i+1].id,point[i+1].x-point[i].x); sort(point+1,point+n+1,cmp2); for(int i=1;i<n;i++)add(point[i].id,point[i+1].id,point[i+1].y-point[i].y); } int main(){ init(); work(); return 0; }
BZOJ4152: [AMPPZ2014]The Captain
原文:https://www.cnblogs.com/Yangrui-Blog/p/9556246.html