P9881 [EC Final 2021] Elden Ring

教授 Pang 正沉迷于一款名为《Elden Ring》的游戏，其中的世界是一个包含 $n$ 个顶点（从 $1$ 到 $n$ 编号）和 $m$ 条无向边的连通图。玩家从顶点 $1$ 开始，穿越世界去击败位于顶点 $n$ 的神。 然而，这并不简单。对于除顶点 $1$ 以外的任何顶点 $i$，都有一个等级为 $l_i$ 的 Boss，玩家以等级 $l_1$ 开始游戏。每天，玩家可以从顶点 $1$ 前往任意顶点 $i$ 并挑战那里的 Boss。如果玩家当前的等级高于 Boss，Boss 将被消灭（失效），玩家的等级将增加 $A$。注意，经过一个有活跃 Boss 的顶点是被禁止的。（换句话说，教授 Pang 可以从顶点 $1$ 前往顶点 $i$，如果在图中存在一条从顶点 $1$ 到顶点 $i$ 的路径，使得该路径上的每个顶点（除了顶点 $i$）都没有活跃的 Boss。）同时，每天开始时，世界上所有剩余的 Boss 的等级都会增加 $B$。 要完成游戏的通关，你需要击败位于顶点 $n$ 的 Boss（Elden Beast）。给定世界的信息，教授 Pang 想知道他至少需要多少天才能做到这一点。 玩家每天只能挑战一个 Boss。

无

无

题面翻译由 ChatGPT-4o 提供。