Submission #4192

#	Time	Username	Problem	Language	Result	Execution time	Memory
4192		cki86201	Following Flow (kriii1_F)	C++98	1 / 1	0 ms	1100 KiB

F

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;

const double EPS = 1e-8;
double mat[32][32];
int N,M;
int out[32];
int cnt[32][32];
double val[32];
double ed[32];

inline double ab(double x){return x>0?x:-x;}

void solve()
{
	int i,j,k;
	for(i=N-1;i>0;i--){
		double tmp = mat[i][i];mat[i][i]=0;
		for(j=i-1;j>=0;j--){
			double t2=mat[j][i]/(1-tmp);
			for(k=i;k>=0;k--)mat[j][k]+=mat[i][k]*t2;
			val[j]+=val[i]*t2;
		}
	}
	printf("%.10f",1/(1-mat[0][0])*val[0]);
}

int main()
{
	scanf("%d%d",&N,&M);
	int i,j;
	for(i=1;i<=M;i++){
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		if(y!=N)mat[x][y]+=1.0;
		out[x]++;
		val[x]+=t;
	}
	for(i=0;i<N;i++){val[i]/=(double)out[i];}
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			mat[i][j]/=(double)out[i];
		}
	}
	solve();
	return 0;
}

• Subtask 1: 1 / 1