oj.uz

Submission #3111

# Submission time Handle Problem Language Result Execution time Memory
3111 2013-08-25T09:38:42 Z ainta Following Flow (kriii1_F) C++
1 / 1
 0 ms 1108 KB 
#include<stdio.h>
int n,m,deg[31],Ed[1001][3];
double w[31][31],C[31],t,t2;
int main()
{
	int i,a,b,j,k;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d%d%d",&Ed[i][0],&Ed[i][1],&Ed[i][2]);
		deg[Ed[i][0]]++;
	}
	for(i=0;i<m;i++){
		a=Ed[i][0],b=Ed[i][1];
		if(b!=n)w[a][b]+=1.0/deg[a];
		C[a]+=1.0*Ed[i][2]/deg[a];
	}
	for(i=n-1;i>0;i--){
		t=1.0/(1.0-w[i][i]);
		w[i][i]=0;
		for(j=i-1;j>=0;j--){
			t2=t*w[j][i];
			w[j][i]=0;
			for(k=i-1;k>=0;k--){
				w[j][k]+=w[i][k]*t2;
			}
			C[j]+=C[i]*t2;
		}
	}
	printf("%.10lf\n",1.0/(1.0-w[0][0])*C[0]);
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1108 KB Output is correct
2 Correct 0 ms 1108 KB Output is correct
3 Correct 0 ms 1108 KB Output is correct
4 Correct 0 ms 1108 KB Output is correct
5 Correct 0 ms 1108 KB Output is correct
6 Correct 0 ms 1108 KB Output is correct
7 Correct 0 ms 1108 KB Output is correct
8 Correct 0 ms 1108 KB Output is correct
9 Correct 0 ms 1108 KB Output is correct
10 Correct 0 ms 1108 KB Output is correct
11 Correct 0 ms 1108 KB Output is correct
12 Correct 0 ms 1108 KB Output is correct
13 Correct 0 ms 1108 KB Output is correct
14 Correct 0 ms 1108 KB Output is correct
15 Correct 0 ms 1108 KB Output is correct