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 翻译