Submission #3891

# Submission time Handle Problem Language Result Execution time Memory
3891 2013-08-31T09:11:03 Z waps12b Following Flow (kriii1_F) C++
0 / 1
4 ms 8192 KB
#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;
	int len;
	Q(int pos_,double dist_,double per_,int len_){
		pos = pos_;
		dist = dist_;
		per = per_;
		len = len_;
	}
};

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

}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1600 KB Output is correct
2 Memory limit exceeded 4 ms 8192 KB Memory limit exceeded
3 Halted 0 ms 0 KB -