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

Solution

定義 \(d_{i,j} = min(x_i - x_j, y_i - y_j)\).

當 \(x_i <= x_j <= x_k\), 發(fā)現 \(d_{i,k} >= d_{i,j} + d_{j,k}\). \(y\) 同理.

因此, 將x軸排序, 將x坐標相鄰的點相連, y軸同理. 求1到n最短路即可.

Code

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<map> using namespace std; #define rep(i,l,r) for(register int i=(l);i<=(r);++i) #define repdo(i,l,r) for(register int i=(l);i>=(r);--i) #define il inline typedef double db; typedef long long ll;//--------------------------------------- const int nsz=2e5+50; const ll ninf=1e17;int n; struct tp{int p,x,y;}line[nsz]; bool cmp1(tp a,tp b){return a.x<b.x;} bool cmp2(tp a,tp b){return a.y<b.y;} int dis(int a,int b){return min(abs(line[a].x-line[b].x),abs(line[a].y-line[b].y));}struct te{int t,v,pr;}edge[nsz*4]; int hd[nsz],pe=1; void adde(int f,int t,int v){edge[++pe]=(te){t,v,hd[f]};hd[f]=pe;} void adddb(int f,int t,int v){adde(f,t,v);adde(t,f,v);}ll mind[nsz],vi[nsz]; struct tnd{ll v,d;}; bool operator<(tnd a,tnd b){return a.d>b.d;} void dij(int f){priority_queue<tnd> pq;rep(i,1,n)mind[i]=ninf,vi[i]=0;mind[f]=0,pq.push((tnd){f,0});int u,d2;while(!pq.empty()){u=pq.top().v;pq.pop();if(vi[u])continue;vi[u]=1;for(int i=hd[u],v;i;i=edge[i].pr){v=edge[i].t,d2=mind[u]+edge[i].v;if(mind[v]>d2){mind[v]=d2;pq.push((tnd){v,mind[v]});}}} } int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;rep(i,1,n)cin>>line[i].x>>line[i].y,line[i].p=i;sort(line+1,line+n+1,cmp1);rep(i,1,n-1)adddb(line[i].p,line[i+1].p,dis(i,i+1));sort(line+1,line+n+1,cmp2);rep(i,1,n-1)adddb(line[i].p,line[i+1].p,dis(i,i+1));dij(1);cout<<mind[n]<<'\n';return 0; }

轉載于:https://www.cnblogs.com/ubospica/p/10237579.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的bzoj4152-[AMPPZ2014]The_Captain的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。