結果

問題 No.298 話の伝達
ユーザー yumakmc
提出日時 2016-02-17 23:00:25
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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