Submission #4029

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4029	2013-08-31T14:03:03 Z	waps12b	Following Flow (kriii1_F)	C++	0 / 1	0 ms	1920 KB

F

#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 = 500;
	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;

}

Subtask #1

0.0 / 1.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	Correct	0 ms	1920 KB	Output is correct
4	Correct	0 ms	1920 KB	Output is correct
5	Correct	0 ms	1920 KB	Output is correct
6	Correct	0 ms	1920 KB	Output is correct
7	Correct	0 ms	1920 KB	Output is correct
8	Incorrect	0 ms	1920 KB	Output isn't correct
9	Halted	0 ms	0 KB	-