HDu 1596確率dijstra
9819 ワード
この問題では,辺権は[0,1]に属し,多段路の長さは各段の積である.dijstraアルゴリズムの特徴に関連して、dijstraのような貪欲な戦略をとることができます.ソース点から最大の距離を選択するたびに、ソース点から他の点までの距離はこの距離より大きくありません.後であるセグメントを加えると、総長さは1以下の数字に乗るので、今選択した距離よりも大きくなることはありません.したがってdijstraアルゴリズムと同様の流れで「最も安全な道」を求めることができる.
1 #include <algorithm>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5 using namespace std;
6
7 const double eps = 1e-4;
8 const int N = 1001;
9 double g[N][N];
10 double dist[N];
11 bool visit[N];
12 int n, m;
13
14 void dij( int s )
15 {
16 memset( visit, false, sizeof(visit) );
17 for ( int i = 0; i <= n; i++ )
18 {
19 dist[i] = 0;
20 }
21 dist[s] = 1;
22 for ( int i = 1; i <= n; i++ )
23 {
24 int u = 0;
25 for ( int j = 1; j <= n; j++ )
26 {
27 if ( !visit[j] && dist[j] > dist[u] )
28 {
29 u = j;
30 }
31 }
32 visit[u] = true;
33 for ( int j = 1; j <= n; j++ )
34 {
35 if ( !visit[j] && g[u][j] > eps )
36 {
37 if ( dist[u] * g[u][j] > dist[j] )
38 {
39 dist[j] = dist[u] * g[u][j];
40 }
41 }
42 }
43 }
44 }
45
46 int main ()
47 {
48 while ( scanf("%d", &n) != EOF )
49 {
50 for ( int i = 1; i <= n; i++ )
51 {
52 for ( int j = 1; j <= n; j++ )
53 {
54 scanf("%lf", &g[i][j]);
55 }
56 }
57 scanf("%d", &m);
58 while ( m-- )
59 {
60 int s, t;
61 scanf("%d%d", &s, &t);
62 dij(s);
63 if ( dist[t] < eps )
64 {
65 printf("What a pity!
");
66 }
67 else
68 {
69 printf("%.3lf
", dist[t]);
70 }
71 }
72 }
73 return 0;
74 }