标签：
【题解】P3645 [APIO2015]雅加达的摩天楼(分层图最短路)感觉分层图是个很灵活的东西
直接连边的话，边数是$O(n^2)$的过不去
然而我们有一个优化的办法，可以建一个新图$G=(V,E)$其中$V$和原图$V$一一对应且连接一个$0$边，此外每个点向V中的$i+-d$连边。
类似网络流的办法瞎建就行了。
过不了uoj
//@winlere #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; inline int qr(){ register int ret=0,f=0; register char c=getchar(); while(c<48||c>57)f|=c==45,c=getchar(); while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar(); return f?-ret:ret; } const int N=90; struct DOGE{unsigned int b:16,p:16;}dg[2]; struct E{ unsigned int to:28,w:15; E(){to=w=0;} E(const int&t,const int&f){to=t; w=f;} }; vector< vector<E> > e; int n,m,cnt; inline void add(const int&fr,const int&to,const int&w){ if(fr>=e.size()) e.resize(fr+1); e[fr].push_back(E(to,w)); } struct SUBGraph{ int begin; SUBGraph(){begin=0;} inline int operator[](int x){return begin+x;} inline void gen(const int&d){ begin=cnt+1; cnt+=n; for(int t=0;t<n;++t){ if(t+d<n) add(begin+t+d,begin+t,1); if(t-d>=0) add(begin+t-d,begin+t,1); add(begin+t,t,0); } } }G[N]; vector<int> d; /* struct cmp{inline bool operator ()(const int&a,const int&b)const{return d[a]>d[b];}}; priority_queue<int,vector<int>,cmp> q; */ queue<int> q; vector<bool> usd; const int inf=1e9; inline void bfs(){ d.resize(cnt+1); usd.resize(cnt+1); for(auto&t:d) t=inf; d[dg[0].b]=0,q.push(dg[0].b); while(q.size()){ int now=q.front(); usd[now]=0; q.pop(); if(now==dg[1].b) continue; for(const auto&t:e[now]){ if(d[t.to]>d[now]+t.w){ d[t.to]=d[now]+t.w; if(!usd[t.to]) q.push(t.to),usd[t.to]=1; } } } } int main(){ n=qr(); m=qr(); cnt=n-1; for(int t=0,p,b;t<m;++t){ b=qr();p=qr(); if(t<2)dg[t].b=b,dg[t].p=p; if(p>=N) for(int i=p,k=1;i<n;i+=p,++k){ if(b-i>=0) add(b,b-i,k); if(b+i< n) add(b,b+i,k); } else { if(!G[p].begin) G[p].gen(p); add(b,G[p][b],0); } } bfs(); printf("%d\n",d[dg[1].b]==inf?-1:d[dg[1].b]); return 0; }【题解】P3645 [APIO2015]雅加达的摩天楼(分层图最短路)
标签：
原文地址：https://www.cnblogs.com/winlere/p/11615532.html