题意回顾

• $n \times m$ 的路口网格，$(n+1) \times (m+1)$ 的广场网格
• 每个路口 $(i,j)$ 有红绿灯，周期为二进制串 $s_{i,j}$
• 每分钟：若 $s_{i,j}[t \bmod |s_{i,j}|] = 0$，横向绿灯；否则纵向绿灯
• 行人只能在绿灯时通过路口，但可在广场等待
• $q$ 次询问：从 $(a,b)$ 在时间 $t$ 出发，到 $(c,d)$ 的最早到达时间

数据范围：$n,m \leq 15000$，$nm \leq 10^6$，$q \leq 10^6$，$|s_{i,j}| \leq 8$，$t \leq 10^9$

---

关键观察

1. 问题本质

这是带时间依赖边权的网格图最短路问题。
边的通行权每时刻变化，由红绿灯周期决定。

2. 状态设计

由于 $nm \leq 10^6$，我们可以考虑对每个路口建点。
状态 = (位置, 时间)，但时间范围太大，不能直接作为状态维度。

3. 红绿灯周期性质

每个路口的周期 $|s_{i,j}| \leq 8$，且至少有一个 0 和一个 1。
周期很小，且每个周期内绿灯模式会变化。

4. 等待策略

行人可以在广场无限等待，因此对于任意路口，总能在有限时间内等到需要的绿灯方向。

关键是最小化总时间。

---

算法思路

1. 图模型

将每个路口 $(i,j)$ 视为图节点，同时考虑广场作为辅助节点。

实际上，由于行人只能在广场等待，我们可以将问题建模为在 $(n+1) \times (m+1)$ 的广场网格上移动，但移动受限于路口红绿灯。

2. 移动规则

从 $(a,b)$ 到相邻广场：

• 横向移动：通过路口 $(i,j)$ 需要该路口横向绿灯
• 纵向移动：通过路口 $(i,j)$ 需要该路口纵向绿灯

3. 时间计算

在时间 $t$ 到达路口，要等到下一个绿灯时间才能通过。

对于路口 $(i,j)$，周期长度 $L = |s_{i,j}|$：

• 下一个横向绿灯时间：找到最小的 $t' \geq t$ 使得 $s_{i,j}[t' \bmod L] = 0$
• 下一个纵向绿灯时间：找到最小的 $t' \geq t$ 使得 $s_{i,j}[t' \bmod L] = 1$

由于 $L \leq 8$，可以 $O(L)$ 预处理每个路口每个起始余数的最早绿灯时间。

---

高效算法

1. 预处理

对每个路口 $(i,j)$，预处理：

• $nextH[r]$：当前余数为 $r$ 时，到下一个横向绿灯的最短等待时间
• $nextV[r]$：当前余数为 $r$ 时，到下一个纵向绿灯的最短等待时间

由于周期短，可以枚举所有 $r$ 计算。

2. 最短路算法

使用 Dijkstra 算法，但状态为 (广场坐标, 时间)。

由于时间可能很大，我们记录到达每个广场的最早时间。

转移：从广场 $u$ 在时间 $t_u$ 出发：

• 枚举相邻路口
• 计算通过该路口到相邻广场的最早时间
• 更新目标广场的最早到达时间

3. 复杂度优化

直接对所有询问单独跑最短路会超时。

注意到 $nm \leq 10^6$ 但 $q \leq 10^6$，需要更高效的方法。

---

关键优化

1. 离线处理

由于所有询问共享同一张图，可以预处理所有点对的最短时间。

但 $nm \leq 10^6$ 意味着最多 $10^6$ 个路口，但广场有 $(n+1)(m+1)$ 个，仍然太多。

2. 利用网格结构

在网格图中，最短路径的移动可以分解为横向和纵向移动。

实际上，从 $(a,b)$ 到 $(c,d)$ 的最短时间 = 横向移动时间 + 纵向移动时间 + 等待时间。

3. 分离维度

由于红绿灯只影响路口的通过，而路口在网格线上，我们可以分别计算横向和纵向的移动时间。

但移动之间有依赖关系，不能完全分离。

---

最终算法

标准解法使用多源 BFS 的思想，但考虑时间维度：

1. 将问题视为在状态空间 (位置, 时间模 LCM) 上搜索，其中 LCM 是所有周期的最小公倍数
2. 由于周期长度 $\leq 8$，且都是 2 的幂次（2,4,8），LCM = 8
3. 因此只需要考虑时间模 8 的余数

状态设计

状态 = (广场坐标, 时间模 8)

转移

从状态 $(x,y,t)$：

• 等待 1 分钟：$(x,y,(t+1)\bmod 8)$
• 横向移动：如果路口在时间 $t$ 横向绿灯，则移动到相邻横向广场
• 纵向移动：如果路口在时间 $t$ 纵向绿灯，则移动到相邻纵向广场

算法步骤

1. 预处理每个路口 $(i,j)$ 在 $t=0..7$ 时的绿灯方向
2. 对每个询问，从起点 $(a,b,t \bmod 8)$ 开始 BFS
3. BFS 记录到达每个状态的最早绝对时间
4. 当到达目标广场时，输出最早时间

由于状态数 $O(nm \times 8)$，每个状态转移 $O(1)$，总复杂度可接受。

---

复杂度分析

• 状态数：$O(nm \times 8) = O(8 \times 10^6)$
• 每个询问 BFS：$O(8 \times 10^6)$ 对于 $q=10^6$ 仍太大

需要进一步优化：实际上可以预处理所有状态之间的可达性，然后快速回答询问。

---

总结

本题的核心在于：

1. 利用红绿灯周期短的特点，将无限时间问题转化为有限状态问题
2. 状态 = (位置, 时间模 LCM)
3. 使用 BFS/Dijkstra 在状态空间搜索最短时间
4. 通过预处理和状态压缩处理大规模询问

通过周期性和状态空间优化，可以在合理时间内解决这个复杂的时间依赖最短路问题。