Submission #3805

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

F

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;


int v[31][1001];
double dist[31][1001];
int cnt[31];

struct Q{
	double per;
	double dist;
	int pos;
	Q(int pos_,double dist_,double per_){
		pos = pos_;
		dist = dist_;
		per = per_;
	}
};

double sum=0;
int main(){
	double lmt = 0.00000001;
	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] ++;
	}
	queue<Q> q;
	q.push(Q(0,0,1));
	while(q.size()){
		Q now = q.front(); q.pop();
		if(now.pos== n){
			sum += now.dist * now.per;
			continue;
		}
		if(cnt[now.pos] == 0)	continue;
		double per = now.per / (double)cnt[now.pos];
		if( per <= lmt)	continue;
		for(int i=0;i<cnt[now.pos];i++)
			q.push(Q( v[now.pos][i] , now.dist + dist[now.pos][i] , per));
	}
	printf("%.10lf\n",sum);
	return 0;

}

• Subtask 1: 0 / 1