#111. 【APIO2015】Jakarta Skyscrapers

印尼首都雅加达市有 NN 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 00 到 N−1N−1。除了这 NN 座摩天楼外，雅加达市没有其他摩天楼。

有 MM 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 00 到 M−1M−1。编号为 ii 的 doge 最初居住于编号为 BiBi 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 ii 的 doge 的跳跃能力为 PiPi （Pi>0Pi>0）。

在一次跳跃中，位于摩天楼 bb 而跳跃能力为 pp 的 doge 可以跳跃到编号为 b−pb−p （如果 0≤b−p<N0≤b−p<N）或 b+pb+p （如果 0≤b+p<N0≤b+p<N）的摩天楼。

编号为 00 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编号为 11 的 doge。任何一个收到消息的 doge 有以下两个选择:

跳跃到其他摩天楼上；
将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 00 号 doge 传递到 11 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 11 号 doge。

输入格式

输入的第一行包含两个整数 NN 和 MM。

接下来 MM 行，每行包含两个整数 BiBi 和 PiPi。

输出格式

输出一行，表示所需要的最少步数。如果消息永远无法传递到 11 号 doge，输出 −1−1。

样例一

input

output

explanation

下面是一种步数为 55 的解决方案：

00 号 doge 跳跃到 22 号摩天楼，再跳跃到 44 号摩天楼（22 步）。
00 号 doge 将消息传递给 22 号 doge。
22 号 doge 跳跃到 33 号摩天楼,接着跳跃到 22 号摩天楼，再跳跃到 11 号摩天楼（33 步）。
22 号 doge 将消息传递给 11 号 doge。

子任务

所有数据都保证 0≤Bi<N0≤Bi<N。

子任务 1 （10 分）
- 1≤N≤101≤N≤10
- 1≤Pi≤101≤Pi≤10
- 2≤M≤32≤M≤3
子任务 2 （12 分）
- 1≤N≤1001≤N≤100
- 1≤Pi≤1001≤Pi≤100
- 2≤M≤20002≤M≤2000
子任务 3 （14 分）
- 1≤N≤20001≤N≤2000
- 1≤Pi≤20001≤Pi≤2000
- 2≤M≤20002≤M≤2000
子任务 4 （21 分）
- 1≤N≤20001≤N≤2000
- 1≤Pi≤20001≤Pi≤2000
- 2≤M≤300002≤M≤30000
子任务 5 （43 分）
- 1≤N≤300001≤N≤30000
- 1≤Pi≤300001≤Pi≤30000
- 2≤M≤300002≤M≤30000

时间限制：1s1s

空间限制：256MB

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define maxn 30010

using namespace std;

int B,num,tot,s,t,head[maxn*],m,n,vis[maxn*],d[maxn*],pos[][maxn];

struct node{int b,p;}a[maxn];

struct Node{int to,pre,v;}e[maxn*];

void Insert(int from,int to,int v){

    e[++num].to=to;

    e[num].v=v;

    e[num].pre=head[from];

    head[from]=num;

}

queue<int>q;

void spfa(){

    for(int i=;i<=tot;i++)d[i]=1e9,vis[i]=;

    q.push(a[].b);

    d[a[].b]=;vis[a[].b]=;

    while(!q.empty()){

        int x=q.front();q.pop();vis[x]=;

        for(int i=head[x];i;i=e[i].pre){

            int to=e[i].to;

            if(d[to]>d[x]+e[i].v){

                d[to]=d[x]+e[i].v;

                if(!vis[to])q.push(to),vis[to]=;

            }

        }

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<m;i++)scanf("%d%d",&a[i].b,&a[i].p);

    tot=n-;

    B=min(,(int)sqrt(n));

    for(int i=;i<=B;i++)

    for(int j=;j<i;j++)

    for(int k=j;k<n;k+=i){

        pos[i][k]=++tot;

        Insert(tot,k,);

        if(k>=i){

            Insert(tot,tot-,);

            Insert(tot-,tot,);

        }

    }

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

        if(a[i].p<=B)

            Insert(a[i].b,pos[a[i].p][a[i].b],);

        else {

            for(int j=;;j++)

                if(j*a[i].p+a[i].b>=n)break;

                else Insert(a[i].b,j*a[i].p+a[i].b,j);

            for(int j=;;j++)

                if(a[i].b-j*a[i].p<)break;

                else Insert(a[i].b,a[i].b-j*a[i].p,j);

        }

    }

    spfa();

    if(d[a[].b]==1e9)puts("-1");

    else printf("%d\n",d[a[].b]);

    return ;

}

doge

uoj #111. 【APIO2015】Jakarta Skyscrapers