[APIO2015] 雅加达的摩天楼 (分块,最短路)

题目链接

Solution

分块+\(Dijkstra\).

难点在于建边,很明显 \(O(n^2)\) 建边会挂一堆 .

那么考虑一下, \(n^2\) 建边多余的是哪些东西 \(???\)

很显然是冗杂的边,即两个点在之前已经可以互达了,但是在这一次仍然又连接一遍.

所以我们对于 \(n\) 个点都开 \(sqrt(n)\) 个辅助点.代表第 \(i\) 个点可以走出 \(j\) .

辅助点之间也需要与相邻的连上一条边权为 \(1\) 的边.

然后对于 \(m\) 个点分类讨论.

如果 \(p_i<sqrt(n)\)

那么在这 \(sqrt(n)\) 里面对应连边.
如果 \(p_i>sqrt(n)\)

那么很显然他所连向的边一般不会有冗杂(大概率).所以直接暴力连边即可.

然后最后面跑一遍 \(Diskstra\) 即可.

注意距离要开 \(long~long\).

Code

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define rg register

#define num(x,y) x*n+y

using namespace std;

const int maxn=30008;

const int inf=0x3f3f3f3f;

struct sj{int to,next; ll w;}a[maxn*500];

int n,m,head[maxn*105],size,s,t,tmp;

int b[maxn],p[maxn];ll dis[maxn*105];

il void add(int x,int y,ll w)

{

     a[++size].to=y;

     a[size].next=head[x];

     head[x]=size;

     a[size].w=w;

}

il int read()

{

    char ch=getchar();int f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

struct node{int u; ll d;

    bool operator <(const node& kkk)const

    {return d>kkk.d;}

};

il void Dijkstra()

{

     priority_queue<node>q;

     memset(dis,127,sizeof(dis));

     q.push((node){s,0});

     dis[s]=0;

     while(!q.empty())

     {

         node x=q.top();q.pop();

         int u=x.u;

         for(int i=head[u];i;i=a[i].next)

         {

             int tt=a[i].to;

             if(dis[tt]>dis[u]+a[i].w)

             {

                 dis[tt]=dis[u]+a[i].w;

                 q.push((node){tt,dis[tt]});

             }

         }

     }

     return;

}

int main()

{

    n=read();m=read();

  	for(int i=1;i<=m;i++) b[i]=read()+1,p[i]=read();

  	s=b[1];t=b[2];

  	tmp=min((int)sqrt(n),100);

  	for(int i=1;i<=tmp;i++)

    for(int j=1;j<=n;j++)

    add(num(i,j),j,0);

  	for(int i=1;i<=tmp;i++)

    for(int j=1;j<=n-i;j++)

    add(num(i,j),num(i,j+i),1),

    add(num(i,j+i),num(i,j),1);

  	for(int i=1;i<=m;i++)

  	{

  		if (p[i]<=tmp) add(b[i],num(p[i],b[i]),0);

  		else

  		{

  			for(ll j=1;b[i]+j*p[i]<=n;j++) add(b[i],b[i]+j*p[i],j);

  			for(ll j=1;b[i]-j*p[i]>=1;j++) add(b[i],b[i]-j*p[i],j);

  		}

  	}

    Dijkstra();

    cout<<(dis[t]>192608173?-1:dis[t])<<endl;

    return 0;

}

巴特西

[APIO2015] 雅加达的摩天楼 (分块,最短路)

题目链接

Solution

Code

最新文章

热门文章