#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=5050;
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;
}
}
printf("%lf",la);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1104 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1104 KB |
Output is correct |
| 3 |
Execution timed out |
400 ms |
1104 KB |
Program timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
