CF605E Intergalaxy Trips
考虑你是不知道后来的边的出现情况的，所以可以这样做：每天你都选择一些点进行观察，知道某天往这些点里面的某条边可用了，你就往这条边走。这样贪心总是对的。
我们定义一个点的权值就是这个点到$n$的期望距离。同时它就是我们要算的答案。
但是注意到一个性质，我们总是从期望较大的点走向期望较小的点（显然的）。
所以我们可以类似反过来的 dijkstra 的更新，维护当前权值的点，然后这个点当前的值就必然是最终这个点的答案。所以我们可以拿它去更新到达它的点。
加入我们当前打算使用点$u$当前我们要考虑所有可以到达$u$的点，这些点已经被某些其他点更新过了。但是我们知道更新这些点的点肯定比$u$小。我们考虑当前枚举一个点$v$，然后尝试用$u$去更新$v$。注意$v$已经被一些点（设为$a_{1\dots n}$） 更新过了，并且$a_{1\dots n}$的权值都小于$u$。
这个时候我们考虑某一天，要么$v$到$a_{1\dots n}$至少一个点有边，这种情况下无论$v$到$u$是否有边都会走到$a_{1\dots n}$。所以真正能够通过$v$走到$u$的情况是某一天$v$到$u$有边并且到其他的点没边。
注意任意选择一个前缀时，等在这个地方的概率不同，是需要计算进去的。
注意$n$只有$10^3$，可以直接跑$O(n^2)$的 dijkstra 跑过去。
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
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "queue"
using namespace std;
#define MAXN 1006
int n;
double p[MAXN][MAXN];
double dp[MAXN] , tmp[MAXN] , f[MAXN];
int vis[MAXN];
int main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i )
for( int j = 1 , q ; j <= n ; ++ j ) scanf("%d",&q) , p[i][j] = 1.0 * q / 100;
for( int i = 1 ; i <= n ; ++ i ) dp[i] = 3e18 , tmp[i] = 1;
dp[n] = 0;
for( int i = 1 , u = 0 ; i <= n ; ++ i ) {
double mn = 3e18;
for( int j = 1 ; j <= n ; ++ j ) if( !vis[j] && dp[j] < mn ) mn = dp[j] , u = j;
vis[u] = 1;
for( int v = 1 ; v <= n ; ++ v ) if( !vis[v] && p[v][u] > 1e-8 ) {
double ls = 1 - tmp[v]; tmp[v] *= 1.0 - p[v][u];
double t = ls / ( 1 - tmp[v] );
double r1 = t * f[v] , r2 = ( 1 - t ) * dp[u];
f[v] = r1 + r2;
dp[v] = min( dp[v] , f[v] + 1 / ( 1 - tmp[v] ));
}
}
printf("%.7lf",dp[1]);
}
|
