Submission #4131

# Submission time Handle Problem Language Result Execution time Memory
4131 2013-09-02T07:41:22 Z waps12b Following Flow (kriii1_F) C++
0 / 1
0 ms 1920 KB
#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;
	for(int i=0;i<=lmt;i++){
		sum += dp[i][n] ;
	}
	printf("%.10lf\n",sum);
	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 -