# 地狱门：题解

## 算法与贡献

[std.cpp](std.cpp)沿用命题者的“带下界松弛、前驱环加速”思路。Codex（GPT-6）补齐规格、证明与测试，明确在触及开放时间时立即断开前驱，并在环加速后重新调度全部环点。另提供独立的[截止时间判定算法](alternative-deadline.cpp)。图构造共用 [portal-graph.hpp](portal-graph.hpp)。

## 先区分三种答案

忽略时间，在世界之间判断可达性。由于可以等待且所有开放时间有限，可达性恰好决定能否到达目标世界。不可达时输出 `YouNeedOpPermission` .

如果目标世界的单步时间为负，可以在目标附近往返任意多次，再走到目标点，因此答案为 `NegativeInfinity` . 若目标世界非负，最后一次传送的到达时间至少为 $t_i+\delta_i\ge-20000$ ；此后移动不能提前。没有使用传送门的路径时间也不会小于0。因此有限答案一定不小于 $-20000$ . 中途经过负时间世界不会自动使最终答案负无穷，因为下一道传送门仍有开放时间。

## 状态图

每道门建立一个状态，表示已到达入口、满足开放时间、准备使用该门的时刻。另设起点和终点两个虚拟状态。若门 $i$ 的出口和门 $j$ 的入口位于同一世界，连边。设曼哈顿距离为 $d_{ij}$ 、该世界步时为 $T$ .

若 $T\ge0$ ，转移为

$$x_j=\max(t_j,x_i+c_{ij}),\qquad c_{ij}=\delta_i+Td_{ij}.$$

若 $T<0$ ，可以先绕行到足够早的时间，再等待到开放，因此直接得到 $x_j=t_j$ ，称为重置边。虚拟状态的传送变化为0、开放时间为足够小的哨兵。起始状态标签从0开始。

![开放时间截断与负时间世界的重置](assets/example.svg)

每个世界至多50个真实入口，故 $V=N+2$ ，$E\le52V$ . 坐标差、乘积、时间标签均用64位整数。

## 标准算法：松弛与负环加速

维护每个状态当前已知可达的最早时间。扫描标签发生变化的点，执行上述转移。若新值等于目标开放时间，清空其前驱；否则记录使其改善的仿射边。重置边一定清空前驱。

前驱图每点至多一条前驱。任何前驱环的总边权都为负：每条前驱在严格改善时建立，沿环的最后一次建立必然闭合一次严格下降。标签之后只会下降，因此始终有 $d_v\ge d_u+c_{uv}$ .

对这样的环，计算

$$\Delta=\min_{u\to v\text{ on cycle}}(d_u+c_{uv}-t_v).$$

若 $\Delta>0$ ，将全部环点标签减去 $\Delta$ ，再把它们全部标记为待扫描。这个值没有跳过开放时间：新的标签不低于每个点的下界。重复绕负环最终可以把每个标签降到这些值或更早，因为在这组新标签上，所有环边仍可作仿射转移，至少一条边的候选值刚好触及开放时间。到达更早时可通过等待实现记录的时刻。若 $\Delta\le0$ ，不平移，正常松弛很快会触及某个下界并断环。

所有有限标签都是整数，真实门有固定下界，虚拟状态仅与有限时间的门或非负移动相连，所以过程终止。停止时所有边均无法改善；沿任意有限操作序列归纳，最终标签不晚于该序列的到达时刻。又因每次更新均可实现，所得答案正是最早时刻。

若总扫描轮数为 $R$ ，时间为 $O(R(E+V))$ ，空间为 $O(E+V)$ . 环加速避免逐圈消耗巨大时间差；这里不把实际轮数误写为无条件常数。正式数据另含长环、单个负边、正时间链及重置边，并与下面有明确多项式界的实现比较。

## 补充方案与取舍

[截止时间判定解法](solution-alternative-deadline.zh.md)和[对应程序](alternative-deadline.cpp)通过二分答案、反向传播最晚出发时间给出独立方案，最坏时间 $O(VE\log(U+20001))$ ，空间 $O(V+E)$ ，其中 $U$ 是一条可行路线的到达时刻。它有直接的多项式界，但需重复判定；标准程序保留出题人的前驱环加速。两者均通过完整数据与当前时限。