CF605E Intergalaxy Trips

科学家们最近发现了虫洞——这些宇宙中的物体可以让我们在星系和星系之间、恒星系之间进行极远距离的旅行。 科学家们已知有 $n$ 个可以到达的星系。你现在位于编号为 $1$ 的星系，需要前往编号为 $n$ 的星系。要从星系 $i$ 到星系 $j$，需要穿越一个虫洞 $(i, j)$，并且恰好在一个星际日后你将到达星系 $j$。 然而，所需的虫洞并不总是可用。每过一天，虫洞会随机出现或消失。但在同一天内，虫洞的状态保持不变。每个星际日，虫洞从星系 $i$ 到星系 $j$ 存在的概率为 $p_{ij}$。在任意时刻，你总是可以查明当前可用的所有虫洞。每一次，你可以选择利用当前可用的虫洞出发前往另一星系，或者选择等待一天，看看本星系第二天会有哪些可通往其他星系的虫洞。 你的任务是求出：若你采取最优策略，从星系 $1$ 到星系 $n$ 所需天数的期望值。保证该期望值存在。

输入的第一行为一个整数 $n$（$1 \leq n \leq 1000$），表示可到达的星系数。 接下来有 $n$ 行，每行 $n$ 个元素。第 $i$ 行第 $j$ 列的元素 $p_{ij}$ 表示从星系 $i$ 到星系 $j$ 的虫洞每天出现的概率（以百分数形式给出，且为整数）。保证所有主对角线上的数值均为 $100$。

输出一个实数，表示在最优策略下，从星系 $1$ 到星系 $n$ 所需天数的期望值。你的答案若与标准答案的绝对误差或相对误差不超过 $10^{-6}$，即视为正确。 即：假定你的答案为 $a$，标准答案为 $b$，则判定条件为 $\frac{|a-b|}{\max(1, |b|)} \leq 10^{-6}$。

在第二个样例中，从星系 $1$ 到星系 $2$ 的虫洞每一天以概率 $0.3$ 出现。期望等待该事件发生所需天数为 $\frac{1}{0.3}$。 由 ChatGPT 5 翻译