Submission #4034

#	Time	Username	Problem	Language	Result	Execution time	Memory
4034		waps12b	Following Flow (kriii1_F)	C++98	0 / 1	0 ms	1920 KiB

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 = 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+1e-9);
	return 0;

}

• Subtask 1: 0 / 1