#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int v[31][1001];
double dist[31][1001];
int cnt[31];
double dp[1000][30];
double per[1000][30];
int main(){
int n, m;scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int a, b;
double t;
scanf("%d %d %lf",&a,&b,&t);
v[a][ cnt[a] ] = b;
dist[a][ cnt[a] ] = t;
cnt[a] ++;
}
per[0][0] = 1.0;
int lmt = 1000;
for(int lv=0;lv<lmt;lv++){
for(int i=0;i<n;i++){
if(!cnt[i]) continue;
double np = 1.0/ (double)cnt[i];
if( np == 0.0) continue;
for(int j=0;j<cnt[i];j++){
int dest = v[i][j];
dp[lv+1][dest] += dp[lv][i] * np + dist[i][j] * np * per[lv][i];
per[lv+1][dest] += np * per[lv][i];
}
}
}
double sum = 0.0;
double persum = 0.0;
for(int i=0;i<=lmt;i++){
sum += dp[i][n] ;
persum += per[i][n];
}
printf("%.10lf\n",sum/persum);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1920 KB |
Output is correct |
| 3 |
Runtime error |
0 ms |
1916 KB |
SIGSEGV Segmentation fault |
| 4 |
Halted |
0 ms |
0 KB |
- |
