题目大意
有一个有$n$个点的有向完全图，每条边每天有一个开放几率$p[i][j]$，给定$p$，你需要求出从$1$到$n$的期望天数
$n \leq 10^3$
分析
我们可以考虑倒着做，类似$\texttt{dijkstra}$的思路，每次找到当前走到$1$期望天数最小的，并用它更新所有点的期望天数和路径概率，直到走到$n$为止。
时间复杂度$\mathcal{O}(n^2)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
const int MaxN = 1e3 + 10;
int n, vis[MaxN], a[MaxN];
double p[MaxN][MaxN], d[MaxN], sum[MaxN], pr[MaxN];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int now = 0;
sum[i] = pr[i] = 1.0;
for (int j = 1; j <= n; j++)
scanf("%d", &now), p[i][j] = now * 0.01L;
}
vis[n] = 1, a[1] = n, d[0] = 1e18;
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (vis[j]) continue;
sum[j] += d[a[i - 1]] * p[j][a[i - 1]] * pr[j];
pr[j] *= (1 - p[j][a[i - 1]]), d[j] = sum[j] / (1 - pr[j]);
}
int pos = 0;
for (int j = 1; j <= n; j++)
if (!vis[j] && d[pos] > d[j])
pos = j;
vis[pos] = 1, a[i] = pos;
}
printf("%.10lf\n", d[1]);
std::cerr << "tiger0132 /qq";
return 0;
}
|