cf1066F Yet Another 2D Walking (贪心+dijkstra)

易证我们走的时候只会从某一层的某端点走向另一端点、然后走向下一层的某端点..

所以建图然后dijkstra就行了

调了一年以后发现dijkstra写错了

 #include<bits/stdc++.h>
#define pa pair<ll,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=4e5+;
const ll inf=1e18; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Edge{
int b,ne;ll l;
}eg[maxn*];
struct Node{
ll x,y,l;
}pos[maxn];
int N,egh[maxn],ect;
ll dd[maxn];
bool flag[maxn];
priority_queue<pa,vector<pa>,greater<pa> > q; inline bool cmp(Node a,Node b){return a.l<b.l;}
inline void adeg(int a,int b,ll l){
eg[++ect].b=b;eg[ect].ne=egh[a];eg[ect].l=l;egh[a]=ect;
}
inline ll dis(int a,int b){return abs(pos[a].x-pos[b].x)+abs(pos[a].y-pos[b].y);} void dijkstra(){
CLR(dd,-);
dd[+N]=;q.push(make_pair(,+N));
while(!q.empty()){
int p=q.top().second;q.pop();
if(flag[p]) continue;
flag[p]=;
for(int i=egh[p];i;i=eg[i].ne){
int b=eg[i].b;
if(dd[b]==-||dd[b]>dd[p]+eg[i].l){
dd[b]=dd[p]+eg[i].l;
q.push(make_pair(dd[b],b));
}
}
}
} int main(){
//freopen(".in","r",stdin);
int i,j,k;
N=rd();
for(i=;i<=N;i++)
pos[i].x=rd(),pos[i].y=rd(),pos[i].l=max(pos[i].x,pos[i].y);
pos[N+].x=,pos[N+].y=,pos[N+].l=;
N++;
sort(pos+,pos+N+,cmp);
int lst1=-,lst2=-;
int la=-,lb=-;
for(i=N,j=N,k=N;i;i){
int aa=-,bb=-;
for(;pos[j].l==pos[i].l&&j;j--){
if(aa==-||pos[j].x<pos[aa].x||(pos[j].x==pos[aa].x&&pos[j].y>pos[aa].y)) aa=j;
if(bb==-||pos[j].y<pos[bb].y||(pos[j].y==pos[bb].y&&pos[j].x>pos[bb].x)) bb=j;
}
if(lst1==-) lst1=aa;
if(lst2==-) lst2=bb;
if(la!=-) adeg(aa+N,la,dis(la,aa)),adeg(bb+N,la,dis(la,bb));
if(lb!=-) adeg(aa+N,lb,dis(lb,aa)),adeg(bb+N,lb,dis(lb,bb));
adeg(aa,bb+N,dis(aa,bb));adeg(bb,aa+N,dis(aa,bb));
la=aa,lb=bb;
}
dijkstra();
printf("%I64d\n",min(dd[lst1+N],dd[lst2+N]));
return ;
}
上一篇:java BitSet2


下一篇:django用户认证