「雅加达的摩天楼」题解

问题分析

有 $M$ 只 doge 分布在 $N$ 座摩天楼上，每只 doge 有初始位置 $B_i$ 和跳跃能力 $P_i$。doge 可以在相邻 $P_i$ 倍数的摩天楼间跳跃（即从 $b$ 到 $b±P_i$）。消息可以从一只 doge 传递给同楼的其他 doge。求从 doge 0 到 doge 1 的最少跳跃步数。

核心建模

这是一个图论最短路问题：

• 节点：需要表示 (摩天楼编号, doge信息)
• 边：两种操作对应两种边
  1. 跳跃：doge 从当前楼跳到另一座楼（消耗1步）
  2. 传递：doge 将消息传递给同楼的其他 doge（消耗0步）

直接建模的问题

如果为每只 doge 在每个可达的楼都建立节点，节点数可能达到 $O(NM)$，对于 $N,M \leq 30000$ 来说太大（$9\times 10^8$）。

优化策略：分块思想

观察

• 当 $P_i$ 较大时，doge 能到达的楼很少（大约 $N/P_i$ 个）
• 当 $P_i$ 较小时，doge 能到达的楼很多，但许多 doge 共享相同的 $P_i$

关键优化

设一个阈值 $S = \sqrt{N}$（约 $173$，当 $N=30000$ 时）

1. 对于 $P_i > S$ 的 doge（大跳跃能力）

• 这些 doge 能到达的楼很少（不超过 $N/S \approx S$ 个）
• 直接建边：从 doge $i$ 的每个可达楼建立边
• 每只 doge 最多建立 $O(N/P_i) = O(S)$ 条边

2. 对于 $P_i \leq S$ 的 doge（小跳跃能力）

• 这些 doge 能到达很多楼，但 $P_i$ 值种类少（只有 $S$ 种）
• 建立辅助节点：对于每个 $(楼编号 b, 跳跃能力 p)$，其中 $p \leq S$
• 辅助节点表示：在楼 $b$，以能力 $p$ 跳跃的状态

3. 边的设计

对于小跳跃能力 doge：

1. doge 进入辅助节点：doge $i$ 在楼 $B_i$，跳跃能力 $P_i$ → 连接到辅助节点 $(B_i, P_i)$，边权为 $0$
2. 从辅助节点跳跃：从 $(b, p)$ 到 $(b±p, p)$，边权为 $1$
3. 从辅助节点退出：从 $(b, p)$ 到楼 $b$ 的所有 doge，边权为 $0$

对于大跳跃能力 doge：

1. 直接跳跃：从 doge $i$ 所在楼 $b$ 到可达楼 $b±kP_i$，边权为 $k$（或建立逐跳的边）

具体实现

数据结构

1. 节点编号分配：

   • 摩天楼节点：$0$ 到 $N-1$
   • 辅助节点：对于每个 $p \leq S$ 和每个 $b$，但实际只需要在访问时动态创建
   • doge 节点：$M$ 只 doge 作为节点

2. 邻接表：存储建好的图

建图过程

步骤1：预处理

• 计算阈值 $S = \sqrt{N}$
• 对每只 doge 按 $P_i$ 分类

步骤2：为小跳跃能力建图

对于每只 $P_i \leq S$ 的 doge $i$：

1. 添加边：doge $i$ → 辅助节点 $(B_i, P_i)$，权值 $0$
2. 辅助节点之间的跳跃边在BFS过程中隐式处理

实际上，我们不需要显式建立所有辅助节点，可以在BFS时动态扩展。

步骤3：为大跳跃能力建图

对于每只 $P_i > S$ 的 doge $i$：

1. 直接建立从 $B_i$ 开始的所有可达楼的边
2. 可以连接到对应楼的 doge 节点

最短路算法

使用 0-1 BFS（双端队列BFS）：

• 跳跃边权值为 $1$，从队尾入队
• 传递边权值为 $0$，从队首入队

空间优化

辅助节点不需要全部预先建立，可以用：

• 数组 vis[b][p] 标记是否访问过状态 $(b, p)$
• 但 $N \times S$ 可能仍然太大（$30000 \times 173 \approx 5.2\times 10^6$），可以接受

算法复杂度分析

时间复杂度

1. 大跳跃能力 doge：每只最多建 $O(N/S)$ 条边，总共 $O(M \cdot N/S)$
   • 当 $M,N \leq 30000, S=173$，最坏 $30000 \times 173 \approx 5.2\times 10^6$
2. 小跳跃能力 doge：每只建 $O(1)$ 条边到辅助节点
3. BFS：每个节点入队一次
   • 总节点数：$N + M + N \times S$（辅助节点）
   • 约 $30000 + 30000 + 5.2\times 10^6 \approx 5.3\times 10^6$

空间复杂度

• 存储图：$O(M \cdot N/S + N \times S)$
• 在 $30000$ 规模下可接受

注意事项

1. 重复 doge：同一座楼可能有多个 doge，包括相同 $P_i$ 的
2. 直接相遇：如果 doge 0 和 doge 1 初始在同一楼，答案为 $0$
3. 不可达情况：如果BFS结束后未访问到 doge 1，输出 $-1$

特殊情况的进一步优化

内存优化技巧

1. 使用 vector 动态存储邻接表
2. 对于辅助节点，使用二维数组 id[b][p] 动态分配编号
3. 对于大 $P_i$，建立边时使用循环，但注意不要重复建立太多边

实际实现细节

算法框架：
1. 读取输入，确定阈值 S = sqrt(N)
2. 为每个 doge 分配节点编号
3. 建立初始边：
   - 对于 P_i ≤ S：连接 doge_i → (B_i, P_i) 辅助节点
   - 对于 P_i > S：从 B_i 向所有可达楼建立边
4. 运行 0-1 BFS
5. 输出答案

总结

本题的关键在于通过分块思想处理不同跳跃能力的 doge：

• 小跳跃能力：使用辅助节点共享跳跃状态，避免重复建边
• 大跳跃能力：直接建边，因为每只 doge 的边数有限

这种优化将复杂度从 $O(NM)$ 降低到 $O((N+M)\sqrt{N})$，能够在题目限制内运行。