# 高阶扩展：把等待周期压成 0-1 状态图

## 本节目标

面对“绿灯内必须连续移动、红灯只能停在安全点”的时间规则，分离完整周期数与本周期已用时间，用 0-1 BFS 取代对绝对时间的搜索。

## 前置知识与课前自测

前置：0-1 BFS、状态图、排序。

1. 若状态只记安全岛编号，会丢失什么？
2. 到达安全岛时绿灯恰好结束，与尚有余量的代价差别是什么？
3. 为什么只向排序后相邻安全岛转移仍不漏最优路线？

<details><summary>答案</summary>

1. 本轮绿灯还剩多少时间。
2. 前者必须经历一次红灯并把轮内进度清零；后者无需新增完整周期。
3. 同方向越过中间安全岛可拆成若干相邻段，总距离和轮内进度不变。

</details>

## 问题动机

以绝对时间建图会把大量只差完整周期数的状态分开；只记位置又无法判断当前绿灯是否还走得动。需要保留“相位”，把完整周期折叠进距离。

## 精选例题：Nastya and Unexpected Guest

### 来源与题意

- VJudge：[CodeForces-1340C](https://vjudge.net/problem/CodeForces-1340C)
- 原题：[Codeforces 1340C](https://codeforces.com/problemset/problem/1340/C)
- 难度：2400；考点：周期状态、0-1 BFS、终点特殊处理

道路是 $[0,n]$，$n\le10^6$；有 $m\le10^4$ 个安全岛，含 0 与 $n$。绿灯 $g$ 秒、红灯 $r$ 秒，$g,r\le1000$。绿灯时每秒走一单位且不能停，只有安全岛可变向；红灯开始时必须在安全岛。求从 0 到 $n$ 的最短时间。

<details><summary>Hint 1</summary>状态设为 `(island, spent)`，其中 `spent` 是当前绿灯已经走的秒数。</details>
<details><summary>Hint 2</summary>让距离只记录已经完整经历的“绿+红”周期数。</details>
<details><summary>Hint 3</summary>移动后 `spent&lt;g` 是 0 边；`spent==g` 必须等待红灯、重置为 0，是 1 边。</details>
<details><summary>Hint 4</summary>到终点即结束；若恰在第 $g$ 秒到达终点，不能把最后一段红灯算进去。</details>

## Observations 与 Editorial

绝对时间可很大，但规则只关心时间在周期中的相位。定义状态 $(i,s)$：人在第 $i$ 个安全岛，当前绿灯已经走 $s$ 秒，$0\le s<g$。距离 `cycle[i][s]` 是此前已经结束并等待过红灯的完整周期数。

从 $i$ 到相邻安全岛 $j$ 距离为 $d$：

- $s+d>g$ 不合法；
- $s+d<g$ 转到 $(j,s+d)$，边权 0；
- $s+d=g$，若还没结束旅程，就必须等红灯并转到 $(j,0)$，边权 1。

边权只有 0/1，用 deque。每弹出状态还单独检查能否在剩余 $g-s$ 秒内直接向右到达 $n$，候选真实时间为

$$
cycle(i,s)(g+r)+s+(n-d_i).
$$

这一步也正确处理“恰好到终点”：到达即停止，不加红灯。

### 正确性证明与复杂度

任一合法行程在每次经过安全岛时产生上述状态；同一绿灯内的连续移动对应若干 0 边，绿灯用满且未结束对应一条 1 边。因此行程映射为状态路径，完整周期数与轮内时间的公式等于真实用时。

反之每条状态边都满足绿灯余量，1 边只在安全岛等待，故状态路径可还原为合法行程。非相邻跳跃可沿同方向经过的中间安全岛拆分，不引入等待或转向，所以只连相邻岛不漏解。0-1 BFS 最小化完整周期数；对同一状态轮内时间固定，故最终枚举得到最短真实时间。

状态数 $O(mg)\le10^7$，每状态至多两条转移，时间与空间均为 $O(mg)$。

## 实现指南、核心伪代码与附件

```text
sort safety islands
dist[start][0] = 0
0-1 BFS over (island i, spent s):
    try finishing directly if n-position[i] <= g-s
    for adjacent island j:
        ns = s + abs(position[j]-position[i])
        if ns < g: relax (j,ns) with cost 0
        if ns == g: relax (j,0) with cost 1
answer = minimum completed*(g+r) + spent + final_distance
```

[完整 GNU C++17 实现](../../参考实现/05-最短路与类最短路/CodeForces-1340C.cpp)

- 状态数组不存 `spent=g`，该相位立即重置。
- 直接把 1 边权写成 `g+r`、0 边写成路长并不能得到普通最短路，因为轮内进度仍约束后续合法性。
- 若绿灯中允许原地等待，则到达安全岛后的可选相位增加，当前唯一进度转移失效。

## 扩展与联系

这是“商作为距离、余数作为状态”的典型模型。若每轮规则由多个阶段组成，可把余数状态改成有限自动机；只有阶段切换代价仍为 0/1 时才能继续使用 0-1 BFS。

## 总结与自检

请复述：为何距离只存周期数仍足够？为何终点不能作为普通 `spent==g` 转移处理？只连相邻安全岛的完备性依赖哪个条件？

## 课后训练建议

先写状态 Dijkstra 验证模型，再替换为 0-1 BFS；用小坐标全时间 BFS 对拍。卡在状态定义 25 分钟后看 Hint 1--2。