結果

問題 No.298 話の伝達
ユーザー yumakmcyumakmc
提出日時 2016-02-17 23:00:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 976 ms / 5,000 ms
コード長 1,278 bytes
コンパイル時間 1,405 ms
コンパイル使用メモリ 167,068 KB
実行使用メモリ 19,868 KB
最終ジャッジ日時 2024-09-22 07:43:23
合計ジャッジ時間 4,878 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 218 ms
19,720 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 8 ms
6,940 KB
testcase_11 AC 266 ms
19,668 KB
testcase_12 AC 143 ms
11,540 KB
testcase_13 AC 319 ms
19,868 KB
testcase_14 AC 148 ms
11,500 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 976 ms
19,808 KB
testcase_17 AC 11 ms
6,940 KB
testcase_18 AC 209 ms
7,568 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 451 ms
11,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

int main() {
	int N, M; cin >> N >> M;
	vector<vector<pair<int, ld>>>edges(N),revedges(N);
	for (int i = 0; i < M; ++i){
		int a, b;ld c; cin >> a >> b >> c;
		c /= 100;
		edges[a].push_back(make_pair(b, c));
		revedges[b].push_back(make_pair(a, c));
	}
	vector<ld>pers(1 << N);
	for (int talk = 0; talk < (1 << N); ++talk){
		bitset<20>bs(talk);
		ld per = 1;
		for (int i = 0; i < N; ++i){
			ld misper = 1;
			bool ok = false;
			if (i == 0){
				if (bs[0]){

					ok = true;
					per *= 1;
				}
				else{
					ok = false;
					per *= 0;
				}
			}else if (bs[i]){
				for (auto e : revedges[i]){
					if (bs[e.first]){
						ok = true;
						misper *= 1 - e.second;
					}
				}
				per *= (1 - misper);
			}
			else{
				for (auto e : revedges[i]){
					if (bs[e.first]){
						misper *= 1-e.second;
					}
				}
				per *= misper;
			}
		}
		pers[talk] =per;
	}
	ld total = 0;
	ld ok = 0;
	for (int talk = 0; talk < (1 << N); ++talk){

		bitset<20>bs(talk);
		if (bs[0]){
			total += pers[talk];
			if (bs[N - 1])ok += pers[talk];
		}
	}
	cout << setprecision(22)<<ok/total << endl;
	return 0;
}
0