結果

問題 No.298 話の伝達
コンテスト
ユーザー chocorusk
提出日時 2019-05-26 10:03:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 232 ms / 5,000 ms
コード長 1,883 bytes
コンパイル時間 815 ms
コンパイル使用メモリ 104,912 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-09-17 15:10:29
合計ジャッジ時間 2,370 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n, m;
bool used[22];
int cmp[22];
vector<P> g[22], gr[22];
vector<int> vs;
int ts[22];
void dfs(int x){
	used[x]=1;
	for(auto p:g[x]){
		if(!used[p.first]) dfs(p.first);
	}
	vs.push_back(x);
}
 
void rdfs(int v, int k){
	used[v]=1;
	cmp[v]=k;
	ts[k]=v;
	for(auto p:gr[v]){
		if(!used[p.first]) rdfs(p.first, k);
	}
}
 
int scc(){
	fill(used, used+n, 0);
	vs.clear();
	for(int i=0; i<n; i++){
		if(!used[i]) dfs(i);
	}
	fill(used, used+n, 0);
	int k=0;
	for(int i=vs.size()-1; i>=0; i--){
		if(!used[vs[i]]) rdfs(vs[i], k++);
	}
	return k;
}

int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a, b, c; cin>>a>>b>>c;
        g[a].push_back({b, c});
        gr[b].push_back({a, c});
    }
    scc();
    double dp[1<<20]={};
    dp[1<<cmp[0]]=1;
    for(int i=(1<<cmp[0])+1; i<(1<<n); i++){
        int j=n-1;
        while(!(i&(1<<j))) j--;
        double p=1;
        for(auto q:gr[ts[j]]){
            if(i&(1<<cmp[q.first])) p*=(1.0-(double)q.second/100);
        }
        dp[i]=dp[i^(1<<j)]*(1-p);
    }
    double ans=0;
    for(int i=1; i<(1<<n); i++){
        if(i&(1<<cmp[n-1])){
            for(int j=0; j<n; j++){
                if(i&(1<<j)){
                    for(auto p:g[ts[j]]){
                        if(!(i&(1<<cmp[p.first]))) dp[i]*=(1.0-(double)p.second/100);
                    }
                }
            }
            ans+=dp[i];
        }
    }
    printf("%.7lf\n", ans);
    return 0;
}
0