【题解】P3645 [APIO2015]雅加达的摩天楼(分层图最短路)

【题解】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;

}