P4745 [CERC2017] Gambling Guide

一个铁路系统由 $n$ 个城市和 $m$ 条双向铁路组成。铁路票只能在安装在每个城市的自动售票机购买。不幸的是，黑客们已经篡改了这些售票机，现在它们有下面的规则： 当 $a$ 市的售票机有一个硬币投入时，机器会发一张从 $a$ 市到随机一个邻市的单程票。 你需要从城市 $1$ 到城市 $n$。你知道机器是怎么工作的并且有一份铁路系统的地图。在每一个城市，当你买了一张票时，你可以选择立即使用它后到达目的地，或者是丢掉它并买一张新票。你可以无限制的购买的票。当你到达城市 $n$，旅行就会结束。 你需要确定一个满足以下条件的策略： - 旅行最终到达终点的概率为 $1$。 - 花在旅行上的硬币的期望值越少越好。 输出这个期望值。

无

无