結果
問題 | No.298 話の伝達 |
ユーザー |
|
提出日時 | 2017-07-17 17:41:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 218 ms / 5,000 ms |
コード長 | 1,617 bytes |
コンパイル時間 | 1,311 ms |
コンパイル使用メモリ | 161,012 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 06:59:44 |
合計ジャッジ時間 | 2,754 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)n;++i) #define each(a, b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define show(x) cout <<#x<<" = "<<(x)<<endl #define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl using namespace std; typedef pair<int,int>P; const int MAX_N = 21; struct edge { int to,cost; }; vector<edge> G[MAX_N]; int main() { int n,m; cin >> n >> m; rep(i,m){ int a,b,c; cin >> a >> b >> c; G[b].pb((edge){a,c}); } double ans = 0; rep(i,1 << (n-2)){ int bf = i; bf <<= 1; bf += (1 << (n-1)); bf += 1; double res = 1; for(int j=1;j<n;j++){ if((bf >> j) & 1){ double tm = 1; rep(k,G[j].size()){ if((bf >> G[j][k].to) & 1){ tm *= (100 - G[j][k].cost) * 0.01; } } res *= (1-tm); }else{ double tm = 1; rep(k,G[j].size()){ if(bf & (1 << G[j][k].to)){ tm *= (100 - G[j][k].cost) * 0.01; } } res *= tm; } } ans += res; } printf("%.10f\n",ans); return 0; }