Submission #3821

#	Time	Username	Problem	Language	Result	Execution time	Memory
3821		Apple_Cplus	Following Flow (kriii1_F)	C++98	0 / 1	8 ms	3284 KiB

F

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
 
using namespace std;

#define MAX 1000

vector<int> adj[33];
vector<int> wht[33];
int n,m;
int out[33];

double dp[33][5555];
bool ck[33][5555];
double go(int u, int dep) {
	if(u == n) return 0;
	if(dep >= MAX) return 0;

	double &ret = dp[u][dep];
	if(ck[u][dep]) return ret;
	ck[u][dep] = 1; ret = 0;

	for(int i=0;i<adj[u].size();++i) {
		int v = adj[u][i];
		int w = wht[u][i];
		ret += (go(v,dep+1) + w) / out[u];
	} return ret;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i) {
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		out[u]++;
		adj[u].push_back(v);
		wht[u].push_back(w);
	} printf("%.10lf",go(0,0));
}

• Subtask 1: 0 / 1