这是 官方题解 的 AI 翻译。

---

EGOI 2025 官方题解 - Currents (水流)

任务作者：Brian Lee Jun Siang

2025 年 7 月 18 日

引言

在本次任务中，给定一个有向图。在某个任意时间点，所有边都会且仅会反转一次。你需要计算从每个节点到出口（反转前是节点 $N-1$，反转后是节点 0）的最短路径，假设反转发生在最不利的时刻。

子任务 1：$M = N-1$ 且 $b_i = a_i + 1$

这个子任务将图限制为一条路径，如下图所示。

考虑一个节点 $i$。在图反转之前，只有一种移动方式，即逐个节点地向节点 $N-1$ 靠近。在图反转之后，同样也只有一种移动方式，即一步步地向节点 0 靠近。

这个子任务的观察点在于，所有边反转的最坏时刻是在到达节点 $N-1$ 的前一步。因此，可以描述出在最坏时刻反转时到达出口的最短路径公式：$dist[i] = N - i - 2 + N - 2$。第一部分 $N - i - 2$ 描述了到节点 $N-2$ 的距离。第二部分 $N - 2$ 描述了从节点 $N-2$ 到位于节点 0 的出口的路径。这个公式可以用一个简单的循环为每个节点计算并打印。

注意有一个边界情况！如果图只包含两个节点，最短路径总是 1，因为在这种情况下，最坏的情况是直接去节点 $N-1$（即本例中的节点 1）然后从那里出去。

子任务 2：每个洞穴都有一条直达洞穴 $N-1$ 的通道

每个节点都有一条到节点 $N-1$ 的直接连接，意味着从每个节点都可以在一步之内到达出口。因此，最短路径的最坏情况总是在你甚至还没开始移动时边就反转了。

对于每个节点，解就是在这个反转后的图中从该节点到节点 0 的最短路径。要计算这个，你可以使用原始图，并从节点 0 运行 Dijkstra 算法，得到所需的最短路径。

注意这里同样有一个边界情况！对于节点 0，最坏的情况是边根本不反转，而必须在 1 步内到达节点 $N-1$。如果像其他节点一样立即反转边，距离会是 0。

---

子任务 3：$N, M \le 2000$

这个子任务旨在考察任何一种具有平方级运行时间的解法。最重要的是，这意味着一个低效的完整解法实现。

子任务 4：有向无环图 (Directed Acyclic Graph)

这个子任务中的图不包含任何环。这允许我们使用动态规划 (DP)。注意，当你位于一个不是出口的节点 $v$ 时，有两种选择：

1. 方向反转现在发生。在这种情况下，我们走最短路径到洞穴 0。
2. 方向反转现在不发生。假设我们已经知道对于每个后继节点，在最坏情况下到达出口需要多长时间，我们现在可以移动到那个时间最小的后继节点。

因此，节点 $v$ 的答案是到 0 的距离与所有后继节点结果加一的最小值中的较大者。这引出了以下的 DP 公式：

$$dp[v] = \max\left(\min_{w \in \text{successors}(v)} (dp[w]) + 1, dist[v]\right)$$

$dist[i]$ 是从节点 0 出发的最短路径。这可以事先用 Dijkstra 算法计算出来。 DP 值可以按逆拓扑序计算。这确保了一个节点的所有后继节点的结果都在该节点的结果计算之前被计算出来。

完整解法

对于完整解法，我们可以使用和前一个子任务相同的思路，但我们不再有拓扑序。为了仍然能高效地计算结果，我们可以调整 Dijkstra 算法，按成本递增的顺序来计算结果：我们不一定需要知道一个节点 $v$ 的所有后继节点的结果来计算 $v$ 的结果，如果我们知道通向最佳可能后继节点的结果就足够了！