問題一覧 > 通常問題

No.298 話の伝達

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 35
作問者 : mayoko_mayoko_
10 ProblemId : 702 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:51

問題文

友達同士で話をしていると,別の友達どうしが,同じ話題で話し始めることがあります。これを競プロっぽくモデル化してみましょう。
N個の友達グループがあり,これらのグループはそれぞれ数字0から$N-1$までの番号がつけられています。
また,これらの友達グループ同士には,合計で$M$個の関係があり,それぞれは整数$A$, $B$, $C$で表されるとします。これは「グループ$A$がある話題を話していると,グループ$B$の人たちは$C$パーセントの確率でその話題を始める」ということを表しています。

今グループ0の人達がyukicoderについて会話を始めました。
この時,グループ$N-1$の人達がyukicoderについて話し始める確率を求めてください。

入力

$N$ $M$
$A_1$ $B_1$ $C_1$
⋮
$A_M$ $B_M$ $C_M$

グループの数$N$,グループ同士の関係の数$M$が1行目に与えられます。 $ 1 \leq N \leq 20$, $1 \leq M \leq N(N-1)/2 $
次の$M$行にはそれぞれ3つの整数$A$,$B$,$C$が与えられます。この意味は上に示したとおり。 $ 0 \leq A_i \leq N-1 $, $0 \leq B_i \leq N-1$, $1 \leq C_i \leq 100$
$A_i \neq B_i$であり,また$i \neq j$のとき$(A_i, B_i) \neq (A_j, B_j)$である。
入力では,あるグループが始めた話題が伝達してそのグループにまた同じ話題が戻ってくることは無いことが保証されている。
関係が定義されてないところの確率は0であるとする。

出力

グループ$N-1$の友達同士がyukicoderについて話しはじめる確率を出力してください。
出力は$10^{-6}$を超える絶対誤差を含んではいけません。
最後に改行してください。

サンプル

サンプル1
入力
4 4
0 1 100
0 2 100
1 3 50
2 3 50
出力
0.75

入力は,グループ0の話は100%グループ1,2に伝達し,またグループ1,2の話はそれぞれ50%の確率でグループ3に伝達することを表しています。 よって,グループ1かグループ2のうち少なくともひとつのグループから話が伝達すればグループ3もyukicoderの話をし始めることになります。この確率は75%です。

サンプル2
入力
4 4
0 1 50
0 2 50
1 3 50
2 3 50
出力
0.4375

サンプル3
入力
5 6
0 1 30
0 2 70
1 2 40
1 3 20
2 4 80
3 4 90
出力
0.6073760000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。