P3645 [APIO2015]雅加达的摩天楼

    • 297通过
    • 1.7K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 SPFA 块状链表,块状数组,分块 最短路 枚举,暴力 APIO 2015 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 $0$ 到 $M − 1$。编号为 $i$ 的 doge 最初居住于编号为 $B_i$ 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 $i$ 的 doge 的跳跃能力为 $P_i$ ($P_i > 0$)。

    在一次跳跃中,位于摩天楼 $b$ 而跳跃能力为 $p$ 的 doge 可以跳跃到编号为 $b − p$ (如果 $0 \leq b − p < N$)或 $b + p$ (如果 $0 \leq b + p < N$)的摩天楼。

    编号为 $0$ 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编

    号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择:

    跳跃到其他摩天楼上;

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

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

    输入输出格式

    输入格式:

    输入的第一行包含两个整数 $N$ 和 $M$。

    接下来 $M$ 行,每行包含两个整数 $B_i$ 和 $P_i$。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    5 3
    0 2
    1 1
    4 1
    输出样例#1: 复制
    5

    说明

    【样例解释】

    下面是一种步数为 $5$ 的解决方案:

    $0$ 号 doge 跳跃到 $2$ 号摩天楼,再跳跃到 $4$ 号摩天楼($2$ 步)。

    $0$ 号 doge 将消息传递给 $2$ 号 doge。

    $2$ 号 doge 跳跃到 $3$ 号摩天楼,接着跳跃到 $2$ 号摩天楼,再跳跃到 $1$ 号摩天楼($3$ 步)。

    $2$ 号 doge 将消息传递给 $1$ 号 doge。

    【数据范围】

    所有数据都保证 $0 \leq B_i < N$。

    子任务 1 (10 分)$1 \leq N \leq 10$

    $1 \leq P_i \leq 10$

    $2 \leq M \leq 3$

    子任务 2 (12 分)$1 \leq N \leq 100$

    $1 \leq P_i \leq 100$

    $2 \leq M \leq 2000$

    子任务 3 (14 分)$1 \leq N \leq 2000$

    $1 \leq P i ≤ 2000$

    $2 \leq M \leq 2000$

    子任务 4 (21 分)$1 \leq N \leq 2000$

    $1 \leq P_i \leq 2000$

    $2 \leq M \leq 30000$

    子任务 5 (43 分)$1 \leq N \leq 30000$

    $1 \leq P_i \leq 30000$

    $2 \leq M \leq 30000$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。