AT_arc016_4 [ARC016D] 軍艦ゲーム

高桥君是舰长。 高桥舰长的任务是从镇守府所在的海域出发，向最终目的地的海域进军。 高桥舰长的行动顺序如下： 1. 航路选择 - 选择进军的航路。如果当前海域没有任何可以前往其他海域的航路，则执行第 4 步的海域离脱。 - 如果当前海域有多条通往其他海域的航路，则由于某种阴谋，每条航路被等概率选择。 - 例如，如果从镇守府所在海域出发，有 4 条通往其他海域的航路，则每条航路被选择的概率为 $25\%$。 2. 进军 - 按照选择的航路，移动到下一个海域。 3. 战斗 - 在进军到的海域 $i$，会遭遇敌舰并发生战斗。 - 从镇守府出港时，高桥舰长率领的军舰体力为 $H$，每次战斗军舰体力会减少 $D_i$。 - 如果军舰体力降为 $0$ 或以下，军舰就会沉没。 - 一旦军舰沉没，高桥舰长会因失意而无法继续出击，因此“绝对不能让军舰沉没”。 - 在镇守府所在海域不会发生战斗，但在最终目的地的海域必定会发生战斗。 4. 海域离脱或返回航路选择 - 海域离脱指的是返回镇守府所在的海域。 - 离脱时，若军舰剩余体力为 $C$，则需要花费 $H-C$ 的时间来恢复体力。 上述“1”、“2”、“3”、“4”每循环一次，消耗 $1$ 单位时间。 ---------------- 关于海域和航路——现在有 $N$ 个海域和 $M$ 条航路。 - 这 $M$ 条航路都是单向的。 因此，对于任意不同的海域 $A,B$，如果有一条航路可以从 $A$ 到 $B$，则不能通过同一条航路从 $B$ 到 $A$。 ---------------- 你是高桥舰长的参谋，你的任务是计算在高桥舰长采取最优策略、消耗的时间最小的情况下，到达最终目的地并在战斗中存活所需的期望时间。 如果无论如何高桥舰长都无法完成任务，则输出 $-1$。 另外，保证不会出现输出期望值大于 $10^6$ 的输入。 输入格式如下，从标准输入读取。 - 第 $1$ 行包含三个整数，分别表示海域数 $N\ (2\leq N\leq 100)$，航路数 $M\ (0\leq M\leq N\cdot(N-1)/2)$，出港时舰队体力 $H\ (1\leq H\leq 100)$，以空格分隔。 - 镇守府所在海域为 $1$，最终目的地海域为 $N$。 - 第 $2$ 行到第 $M+1$ 行，每行两个整数 $f_i\ (1\leq f_i\leq N)$、$t_i\ (1\leq t_i\leq N)$，表示第 $i$ 条航路的起点和终点，以空格分隔。 - 保证 $f_i < t_i$。 - 第 $M+2$ 行到第 $M+N+1$ 行，每行一个整数 $D_i\ (0\leq D_i\leq 100)$，表示在第 $i$ 个海域战斗时受到的伤害。 - $D_1$ 的值总是 $0$（即镇守府所在海域）。 - 保证不会出现输出期望值大于 $10^6$ 的输入。 请输出在高桥舰长采取最优策略、消耗的时间最小的情况下，到达最终目的地并在战斗中存活所需的期望时间。 如果无论如何无法完成任务，则输出 $-1$。 输出的绝对误差或相对误差至少有一项不超过 $10^{-6}$。 输出末尾需换行。 - 例如，从镇守府 $1$ 到最终目的地 $6$ 有两条路径： 1. 1 $\to$ 2 $\to$ 4 $\to$ 6 - 该路径被选择的概率为 $50\%$。 - 该路径军舰受到的总伤害为 $0+1+2+4=7$。 - 该路径消耗的时间为 $3$（即循环 $3$ 次）。 2. 1 $\to$ 3 $\to$ 5 $\to$ 6 - 该路径被选择的概率为 $50\%$。 - 该路径军舰受到的总伤害为 $0+1+3+4=8$。 - 出港时军舰体力为 $8$，因此会沉没。 - 高桥舰长会在海域 $3$ 战斗结束后选择海域离脱。 - 该路径消耗的时间为 $1$（循环 $1$ 次）$+$ 体力恢复时间 $=1+1=2$。 即，1 $\to$ 3 $\to$ 5 $\to$ 6 路径上“撤退一次”后，再走 1 $\to$ 2 $\to$ 4 $\to$ 6——有 $50\%$ 的概率走 1 $\to$ 3 $\to$ 5 $\to$ 6，消耗 $2$ 单位时间返回镇守府。 之后有 $50\%$ 的概率走 1 $\to$ 2 $\to$ 4 $\to$ 6，消耗 $3$ 单位时间到达最终目的地。 即，有 $25\%$ 的概率用 $5$ 单位时间到达最终目的地。 如果在 1 $\to$ 3 $\to$ 5 $\to$ 6 路径上“撤退两次”后，再走 1 $\to$ 2 $\to$ 4 $\to$ 6，则有 $12.5\%$ 的概率用 $7$ 单位时间到达最终目的地。 如果在 1 $\to$ 3 $\to$ 5 $\to$ 6 路径上“撤退三次”后，再走 1 $\to$ 2 $\to$ 4 $\to$ 6，则有 $6.25\%$ 的概率用 $9$ 单位时间到达最终目的地。 由此可知，所求的期望值为 $3\times 0.5+5\times 0.25+7\times 0.125+\ldots=5$。

无

无

无 由 ChatGPT 4.1 翻译