Submission #4013

#	Time	Username	Problem	Language	Result	Execution time	Memory
4013		Qwaz	Following Flow (kriii1_F)	C++98	0 / 1	0 ms	1212 KiB

F

#include <cstdio>
#include <vector>
#include <queue>

const int N_MAX=35, M_MAX=1020;
const double EPSILON=2.2204460492503131e-016;

struct state {
	int time, node;
	double ratio;

	bool operator < (const state &t) const {
		return time*ratio > t.time*t.ratio;
	}
};

struct edge {
	int to, time;
};

int n, m, outCount[N_MAX];
std::vector < edge > to[N_MAX];

void input(){
	scanf("%d%d", &n, &m);

	int i;
	for(i=0; i<m; i++){
		int p, q, r;
		scanf("%d%d%d", &p, &q, &r);

		edge t;
		t.time = r;
		t.to = q;
		to[p].push_back(t);
	}
}

std::priority_queue < state > pq;
double res;

void solve(){
	state now;

	now.node = 0;
	now.ratio = 1;
	now.time = 0;

	pq.push(now);

	while(true){
		now = pq.top();
		pq.pop();

		if(now.ratio < EPSILON)
			break;

		int i, size=to[now.node].size();
		for(i=0; i<size; i++){
			int next = to[now.node][i].to;
			int edgeTime = to[now.node][i].time;

			state sNext;
			sNext.node = next;
			sNext.ratio = now.ratio/size;
			sNext.time = now.time+edgeTime;

			if(next == n)
				res += sNext.ratio*sNext.time;
			else
				pq.push(sNext);
		}
	}

	printf("%.10lf\n", res);
}

int main(){
	input();

	solve();

	return 0;
}

• Subtask 1: 0 / 1