# 地狱门：截止时间判定解法

Codex（GPT-6）提供不同方向的最优性判定，实现于 [alternative-deadline.cpp](alternative-deadline.cpp)。[主解法](solution.zh.md)保留出题人的前驱环加速。两者均通过完整测试；本方案有明确的多项式最坏界，但需要多次判定。

## 共用模型

每个门的状态是满足开放时间后的就绪时刻，另有虚拟起点与终点。非负步时世界的边为 $x_v=\max(t_v,x_u+c_{uv})$ ；负步时世界的边直接重置为 $t_v$ . 图有 $V=N+2$ 个点、$E\le52V$ 条边。先处理目标不可达和目标世界步时为负的情况；详细建模见[主解法](solution.zh.md)。

## 判定与二分


给定终点截止时间 $X$ ，反向维护每个状态仍能按时到达终点的最晚就绪时间 $L_u$ . 从终点 $L=X$ 开始；反向经过仿射边得到 $L_u=L_v-c_{uv}$ ，只有结果不早于 $t_u$ 才可用。若从起点获得 $L_0\ge0$ ，判定成功。

若反向到达一个正向可达的重置边，其源状态无论多晚都可以先在负时间世界绕行，判定也成功。若连续 $V$ 轮仍有改善，则存在反向增益为正的环；反复绕环可容纳任意晚的进入时刻。该环正向可达，起点能等待足够久后进入，所以仍判成功。无增益环的见证可以去环成至多 $V-1$ 条边的简单路径，故轮数判据充分且必要。

在 $[-20000,U]$ 上二分，$U$ 由任意一条世界可达路径的实际行走时刻给出。复杂度 $O(VE\log(U+20001))$ ，空间 $O(V+E)$ . 此实现使用不同方向的可行性判定，可用于交叉验证；它的最坏界更直接，但要重复多次判定。两种实现均通过本轮正式时限，详见[数据说明](tests/README.md)。