首页 > 代码库 > BZOJ4070: [Apio2015]雅加达的摩天楼
BZOJ4070: [Apio2015]雅加达的摩天楼
思路{
对于一条楼上的每一条狗.最直观的方法是把一个点拆成N条狗的点,然后最短路即可。
然而炸空间我也是醉了。
因此我们要用到一个调调的分块优化。
应当是每个点的连通状态。意会一下。
把一座楼分成1-块长层,那对于任意相同层数的狗可以在高空乱JB走。
但连通长度p>块长的呢?------直接连边就可以了。
然后YY一下,处理每条狗的激活关系。SPFA就可以了。
}
#include<bits/stdc++.h> #define RG register #define il inline #define N 5500000 #define Inf 2 #define U unsigned short #define pos(i,j) (i*n+j) using namespace std; struct ed{int nxt,to,c;}e[30005*500]; int head[30005*105],dis[30005*105],n,m,q,b,s,t;bool in[30005*105];int tot; void add(int u,int v,int c){e[tot].nxt=head[u];e[tot].to=v;e[tot].c=c;head[u]=tot++;} void ADD(int u,int v,int c){add(u,v,c),add(v,u,c);} void spfa(){ queue<int>que;memset(dis,Inf,sizeof(dis));int SS=dis[t]; que.push(s),in[s]=true,dis[s]=0; while(!que.empty()){ int u=que.front();que.pop();in[u]=false; for(int i=head[u];i!=-1;i=e[i].nxt)if(dis[e[i].to]>dis[u]+e[i].c){ int v=e[i].to;dis[v]=dis[u]+e[i].c; if(!in[v])que.push(v),in[v]=true; } }if(dis[t]==SS)cout<<"-1"; else cout<<dis[t]; } int main(){ freopen("skyscraper.in","r",stdin); freopen("skyscraper.out","w",stdout); memset(head,-1,sizeof(head)); cin>>n>>m;U int len=min((int)sqrt(n),100); for(RG int i=1;i<=len;++i)for(int j=1;j<=n;++j)add(pos(i,j),j,0); for(RG int i=1;i<=len;++i)for(int j=1;j<=n-i;++j)ADD(pos(i,j),pos(i,j+i),1); for(RG int i=1;i<=m;++i){int b,p; cin>>b>>p;b++; if(i==1)s=b;if(i==2)t=b; if(p<=len)add(b,pos(p,b),0); else { for(int j=1;j*p+b<=n;++j)add(b,b+j*p,j); for(int j=1;b-j*p>0;++j)add(b,b-j*p,j); } }spfa(); return 0; }
BZOJ4070: [Apio2015]雅加达的摩天楼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。