GitHub 源文件 Markdown English

地狱门：题解

算法与贡献

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

每个世界至多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)\) . 环加速避免逐圈消耗巨大时间差；这里不把实际轮数误写为无条件常数。正式数据另含长环、单个负边、正时间链及重置边，并与下面有明确多项式界的实现比较。

补充方案与取舍

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