結果
問題 | No.298 話の伝達 |
ユーザー |
![]() |
提出日時 | 2015-11-06 22:45:05 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,276 bytes |
コンパイル時間 | 1,784 ms |
コンパイル使用メモリ | 160,496 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-13 13:23:58 |
合計ジャッジ時間 | 2,278 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 11 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef signed long long ll;#undef _P#define _P(...) (void)printf(__VA_ARGS__)#define FOR(x,to) for(x=0;x<to;x++)#define FORR(x,arr) for(auto& x:arr)#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)#define ALL(a) (a.begin()),(a.end())#define ZERO(a) memset(a,0,sizeof(a))#define MINUS(a) memset(a,0xff,sizeof(a))//-------------------------------------------------------int N,M;int mat[21][21];int rr[21][21];double pat[21];void solve() {int i,j,k,l,r,x,y,z; string s;cin>>N>>M;FOR(i,N) FOR(j,N) mat[i][j]=100;FOR(i,N) mat[i][i]=0;FOR(i,M) {cin>>x>>y>>r;rr[x][y]=r;mat[x][y]=1;}FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);FOR(i,N) pat[i]=-1;pat[0]=1;for(i=1;i<3*N;i++) {FOR(x,N) if(pat[x]==-1) {int ok=1;FOR(y,N) if(mat[y][x]==1 && pat[y]==-1) ok=0;if(ok) {pat[x]=1;FOR(y,N) if(mat[y][x]==1) {pat[x] *= (100-pat[y]*rr[y][x])/100.0;}pat[x]=1-pat[x];}}}_P("%.12lf\n",pat[N-1]);}int main(int argc,char** argv){string s;int i;if(argc==1) ios::sync_with_stdio(false);FOR(i,argc-1) s+=argv[i+1],s+='\n';FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);solve(); return 0;}