Submission #3876

#TimeUsernameProblemLanguageResultExecution timeMemory
3876pichuliaFollowing Flow (kriii1_F)C++98
0 / 1
400 ms1104 KiB
#include<stdio.h> int n,m; int a[35][35][3]; int an[35]; int an2[35]; double d1[3][35]; double d2[3][35]; double la; int main(){ int i,j,k,in1,in2,in3; scanf("%d %d",&n,&m); for(i=1;i<=m;i++){ scanf("%d %d %d",&in1,&in2,&in3); if(in1!=n){ a[in2][++an[in2]][0]=in1; a[in2][an[in2]][1]=in3; an2[in1]++; } } d1[0][0]=1; int i1,i2; double op,d1n=0,d2n=0; int in=8000; for(i=1;i<=in;i++){ i1=i%2; for(j=0;j<=n;j++){ d1[i1][j]=d2[i1][j]=0; for(k=an[j];k>=1;--k){ if(an2[a[j][k][0]]!=0) d1[i1][j]+=d1[(i1+1)%2][a[j][k][0]]/(double)an2[a[j][k][0]]; } for(k=an[j];k>=1;--k){ if(an2[a[j][k][0]]!=0 && d1[i1][j]!=0) d2[i1][j]+=(a[j][k][1]+d2[(i1+1)%2][a[j][k][0]])*(d1[(i1+1)%2][a[j][k][0]]/(double)an2[a[j][k][0]])/d1[i1][j]; } // printf("%lf ",d2[i1][j]); } //getchar(); la+=d1[i1][n]*d2[i1][n]; d1n+=d1[i1][n]; if(d2[i1][n]>d2n) d2n=d2[i1][n]; if(i==in){ la+=(1-d1n)*d2n*4/3; } } printf("%lf",la); }
#Verdict Execution timeMemoryGrader output
Fetching results...