답안 #3805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3805 2013-08-31T08:26:41 Z waps12b Following Flow (kriii1_F) C++
0 / 1
0 ms 4260 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;
	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;

}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1600 KB Output is correct
2 Incorrect 0 ms 4260 KB Output isn't correct
3 Halted 0 ms 0 KB -