TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3316
  • 問題
  • P3316【APIO2015】雅加达的摩天楼
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,256m
    問題説明

      印尼首都雅加达市有N座摩天楼,它们排列成一条直线,我从左到右依次将它们编号为0到N-1。除了这N座摩天楼外,雅加达市没有其他摩天楼。
        有M只叫做“doge”的神秘生物在雅加达市居住。它们的编号一次是0到M-1。编号为i的doge最初居住于标号为Bi的摩天楼。每只doge都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为i的doge的跳跃能力为Pi(Pi>0)。在一次跳跃中,位于摩天楼 b 而跳跃能力为 p 的 doge 可以跳跃到编号为 b−p (如果 0≤b−p<N)或 b+p (如果 0≤b+p<N)的摩天楼。。
        编号为0的doge是所有doge的首领,它有一条紧急的消息要尽快传送给编号为1的doge。任何一个收到消息的doge有以下两个选择:
        1.跳跃到其他摩天楼上;
        2.将消息传递给它当前所在的摩天楼上的其他doge。
        请帮助doge们计算将消息从0号doge传递到1号的doge所学要的最少总跳跃步数,或者告诉他们消息永远不可能传递到1号doge。

    入力形式

     输入的第一行包含两个整数N和M,接下来M行,每行包含两个整数Bi和Pi。

    出力形式

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

    サンプル入力

    5 3
    0 2
    1 1
    4 1

    サンプル出力

    5

    ヒント

          下面是一种步数为5的解决方案:
        0号doge跳跃到2号摩天楼,再跳跃到4号摩天楼(2步)。
        0号doge将消息传递给2号doge。
        2号doge跳跃到3号摩天楼,接着跳跃到2号摩天楼,再跳跃到1号摩天楼(3步)。
        2号doge将消息传递给1号doge。
    数据规模和约定
        共有五部分数据(或称为5个子任务)。所有数据都保证0≤Bi<N。
        第1部分数据占10分,数据范围满足:1≤N≤10,1≤Pi≤10,2≤M≤3;
        第2部分数据占12分,数据范围满足:1≤N≤100,1≤Pi≤100,2≤M≤2000;
        第3部分数据占14分,数据范围满足:1≤N≤2000,1≤Pi≤2000,2≤M≤2000;
        第4部分数据占21分,数据范围满足:1≤N≤2000,1≤Pi≤2000,2≤M≤30000;
        第5部分数据占43分,数据范围满足:1≤N≤30000,1≤Pi≤30000,2≤M≤30000。