正解:最短路+优化连边
解题报告:
这种优化连边啥的真的好妙噢$QwQ$
首先显然离散化下不说$QwQ$.然后对所有横坐标纵坐标分别建点,相邻两横坐标点相连,边权为离散前的坐标差.纵坐标同理.
然后对给定的点,连向对应的横纵坐标,边权为0,跑个最短路就完事$QwQ$
正确性显然?不说了$QwQ$
#include<bits/stdc++.h> using namespace std; #define il inline #define lf double #define gc getchar() #define mp make_pair #define int long long #define P pair<int,int> #define t(i) edge[i].to #define w(i) edge[i].wei #define ri register int #define rc register char #define rb register bool #define lowbit(x) (x&(-x)) #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) #define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) #define lbh(x) lower_bound(sth+1,sth+1+h_cnt,x)-sth #define lbl(x) lower_bound(stl+1,stl+1+l_cnt,x)-stl const int N=5e6+10; int n,h_cnt,sth[N],l_cnt,stl[N],ed_cnt,head[N],S,T,dis[N],vis[N]; struct node{int x,y;}nod[N]; struct ed{int to,nxt,wei;}edge[N<<2]; priority_queue< P,vector<P>,greater<P> >Q; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il void ad(ri x,ri y,ri z){/*printf("%d %d %d ",x,y,z);*/edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;} il void dij() { memset(dis,63,sizeof(dis));dis[S]=0;Q.push(mp(0,S)); while(!Q.empty()) { ri nw=Q.top().second;Q.pop();if(vis[nw])continue;vis[nw]=1; //printf("nw=%d dis=%d ",nw,dis[nw]); e(i,nw)if(dis[t(i)]>dis[nw]+w(i))dis[t(i)]=dis[nw]+w(i),Q.push(mp(dis[t(i)],t(i))); } } signed main() { //freopen("4152.in","r",stdin);freopen("4152.out","w",stdout); n=read();rp(i,1,n)nod[i]=(node){sth[++h_cnt]=read(),stl[++l_cnt]=read()}; sort(sth+1,sth+1+h_cnt);h_cnt=unique(sth+1,sth+h_cnt+1)-sth-1;rp(i,1,n)nod[i].x=lbh(nod[i].x); sort(stl+1,stl+1+l_cnt);l_cnt=unique(stl+1,stl+l_cnt+1)-stl-1;rp(i,1,n)nod[i].y=lbl(nod[i].y); rp(i,2,h_cnt)ad(i,i-1,sth[i]-sth[i-1]),ad(i-1,i,sth[i]-sth[i-1]); rp(i,2,l_cnt)ad(i+h_cnt,i-1+h_cnt,stl[i]-stl[i-1]),ad(i-1+h_cnt,i+h_cnt,stl[i]-stl[i-1]); rp(i,1,n){ri t1=i+h_cnt+l_cnt,t2=nod[i].y+h_cnt;ad(t1,nod[i].x,0),ad(nod[i].x,t1,0),ad(t1,t2,0),ad(t2,t1,0);} S=1+h_cnt+l_cnt;T=n+h_cnt+l_cnt;dij();printf("%lld ",dis[T]); return 0; }