完全图，(1 leq n leq 1000)每一天边有 (p_{i,j}=frac{A_{i,j}}{100}) 的概率出现，可以站在原地不动，求 (1) 号点到 (n) 号点期望天数。
注意 Windows 下 double 读入异常地慢，而自己 Linux 下读入巨快……
首先，每个点肯定都会往期望更小的点走。如果目标点期望比自己大，还不如原地不动。
所以点构成了一个全序关系。显然对于每个点，它的决策是确定的。
所以当确定一个点的最小期望值时，需要确定一个排列 (P) 使得方程解出来的 (E_1) 最小，且 (E_{P_i}) 随着 (i) 增加单调不降：
[E_{P_i} = sum_{j leq i} E_{P_j} cdot p_{P_i,P_j} cdot prod_{k<j} left( 1 - p_{P_i,P_k}
ight)
]
但是这样考虑太麻烦了，我们考虑倒着做：因为当 (i) 越小时， (E_{P_i}) 的式子越简单。
因此考虑从 (n) 号点往回递推，当我们确定 (P_i) 时，对于每个点，它的式子前几项都已经求出来了，对 (j = i) 移项，每次取能解出的最小的 (E)。即 dijkstra 地求。
需要类似前缀和优化的技巧。
考虑正确性：
不妨假设最终的 (E_i) 互不相同。
我们假设确定 (P_i) 时最小的那个叫 (A)，然而我们顶替了一个 (E) 更大的 (B) 上去，那么 (A) 可以不走到 (P_j (j geq i)) 的点达到更优解，那么就发生了 (E_A < E_B)，全序关系被破坏，矛盾。
#include <bits/stdc++.h>
const int MAXN = 1010;
double P[MAXN][MAXN];
double E[MAXN], prod[MAXN], dis[MAXN];
bool vis[MAXN];
int n;
int main() {
std::ios_base::sync_with_stdio(false), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1, t; j <= n; ++j)
std::cin >> t, P[i][j] = t / 100.;
for (int i = 1; i < n; ++i)
dis[i] = 1e100, E[i] = prod[i] = 1;
dis[n] = 0;
for (int i = 1; i <= n; ++i) {
int at = 0;
for (int j = 1; j <= n; ++j)
if (!vis[j] && (!at || dis[at] > dis[j])) at = j;
vis[at] = true;
for (int j = 1; j <= n; ++j) if (!vis[j]) {
E[j] += dis[at] * prod[j] * P[j][at];
prod[j] *= 1 - P[j][at];
dis[j] = E[j] / (1 - prod[j]);
}
}
std::cout << std::fixed << std::setprecision(15) << dis[1] << std::endl;
return 0;
}