CF605E Intergalaxy Trips 题解

题意：

给定 $n$ 个点的有向完全图。

$i \to j$ 的边每天出现的概率均为 $p_{i,j}$，若 $i = j$，有 $p_{i,j} = 1$。

每天可以选择一条存在的出边走过去或停留在原地不动。

求最优策略下从 $1$ 到 $n$ 的期望天数，$n \le 10^3$。

完整题意：

最近，科学家们发现了虫洞 —— 宇宙中的一种物体，可以让你在星系和恒星系统之间旅行很长的距离。

科学家们知道有 $n$ 个星系可以到达。你位于星系编号 $1$，你需要到达星系编号 $n$。从星系 $i$ 到星系 $j$，你需要乘坐虫洞 $(i,j)$，并在恰好一个星系日内，你将出现在星系 $j$。

不幸的是，所需的虫洞并不总是可用的。每个星系日它们会随机消失和出现。然而，虫洞的状态在一个星系日内不会改变。从星系 $i$ 到星系 $j$ 的虫洞每天分别存在的概率为 $p_{ij}$。你可以随时了解当前存在哪些虫洞。在每个时刻，你可以选择通过现有虫洞之一前往另一个星系，或者你可以等待一个星系日，看看哪些虫洞将在第二天将你带到下一个位置。

你的任务是找到从星系 $1$ 到星系 $n$ 旅行所需时间的期望值，如果你采取最佳方式行动。保证该期望值存在。

输入格式：

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$）—— 可以到达的星系数量。

然后是一个 $n$ 行 $n$ 列的矩阵。每个元素 $p_{ij}$ 代表从星系 $i$ 到星系 $j$ 存在虫洞的概率。所有概率以百分比表示，为整数。保证主对角线上的所有元素均为 $100$。

输出格式：

输出一个实数值 —— 如果采取最佳方式行动，从星系 $1$ 到星系 $n$ 旅行所需时间的期望值。你的答案将被视为正确，如果其绝对或相对误差不超过 $10^{-6}$。

具体来说：假设你的答案是 $a$，而评审的答案是 $b$。检查程序将认为你的答案是正确的，如果 $\frac{|a-b|}{\max(1, b)} \leq 10^{-6}$。

考虑设 $f_i$ 为 $i \to n$ 的期望耗时，那么显然我们不会跑到一个 $f_j > f_i$ 的地方碰运气。

因此我们只需要考虑比它更优的点。那么什么是更优的点呢？就是所有冒出来的边 $(i,j)$ 中 $f_j$ 最小的那个 $j$

考虑用转移方程的形式描述这个过程：

$f_i=\sum_j^{f_j<f_i} p_{i, j} f_j \prod_k^{f_k<f_j}\left(1-p_{i, k}\right)+f_i \prod_j^{f_j<f_i}\left(1-p_{i, j}\right)+1$

第一部分枚举 $j$ ， $j$ 的限制就是没有 $k(k\ne j)$ 满足 $f_k < i$ 且 $(i,k)$ 存在。

第二部分就是实在找不出这么个 $j$ 能走了，那就在原地绕一圈。第三部分的 $1$ 很好理解吧。

则移项可得

$f_i=\frac{\sum_j^{f_j<f_i} p_{i, j} f_j \prod_k^{f_k<f_j}\left(1-p_{i, k}\right)+1}{1-\prod_j^{f_j<f_i}\left(1-p_{i, j}\right)}$

这个方程直接枚举看上去没法优化，因此我们不妨观察一下有什么特殊性质。

首先容易发现每次更新 $i$ 的 $j$ ，显然在每次更新后是单调不增的，并且 $f_i$ 一定大于 $f_j$ 。

那么如果我们找到一个最小的 $f_x$ 作为 $f_j$ ，然后去更新其他的 $f_i$ ，是不是就可以了呢？

这个过程有点像 Dijkstra ，每次找出最小的 $u$ ，去尝试更新所有相邻的 $v$ 。

不妨记 $g_i$ 为分数线上面一坨， $h_i = \prod_j^{f_j<f_i}\left(1-p_{i, j}\right)$ ，即 $f_i = \dfrac{g_i}{1 - h_i}$ 。

具体地，我们将 $f_i,g_i,h_i(i<n)$ 初始都设为 $1$ ，并把 $n$ 作为初始的 $j$ ，

然后每轮都枚举未被作为 $j$ 过的 $i$ ，通过新考虑 $(i,j)$ 的贡献（注意是有向完全图，所以不是 $(j,i)$ ）

如果按 $g_i,h_i,f_i$ 依次更新的话，那么在 $h_i$ 被 $j$ 更新之前，可以通过 $g_i\gets g_i + p_{i,j}f_jh_i$ 以达到目的。

因为这时的 $h_i$ 就等于 $\prod_k^{f_k<f_j}\left(1-p_{i, k}\right)$ ，换句话说，截止到 $j$ ，其他所有已经考虑过的点 $k$ 都有 $f_k < f_j$

时间复杂度 $\mathcal{O}(n^2)$ ，注意不要用 cin 读 double 型数据，否则会 TLE

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

int n,cnt,q[N]; char vis[N];
double p[N][N],f[N],g[N],h[N];
void upd()
{
    int j = q[cnt];
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        g[i] += f[j] * p[i][j] * h[i];
        h[i] *= 1 - p[i][j]; f[i] = g[i] / (1 - h[i]);
    }
}
void solve()
{
    for(int i = 1; i < n; i++) f[i] = g[i] = h[i] = 1;
    f[n] = 0; h[n] = 1; vis[n] = true; q[++cnt] = n; upd();
    for(; cnt < n; ) {
        int id; double v = INF;
        for(int i = 1; i <= n; i++)
            if(!vis[i] && f[i] < v) v = f[i], id = i;
        vis[id] = true; q[++cnt] = id; upd();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; if(n == 1) return cout << "0\n", 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1, x; j <= n; j++) cin >> x, p[i][j] = x / 100.0;
    solve(); cout << fixed << setprecision(8) << f[1] << '\n';
    return 0;
}