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

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

共用模型¶

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

判定与二分¶

给定终点截止时间 \(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)\) . 此实现使用不同方向的可行性判定，可用于交叉验证；它的最坏界更直接，但要重复多次判定。两种实现均通过本轮正式时限，详见数据说明。