记录编号	428397	评测结果	AAAAAAAAAA
题目名称	[Nescafe19] 绿豆蛙的归宿	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.209 s
提交时间	2017-07-25 15:58:14	内存使用	5.37 MiB

#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

const int MAXE=200010;
const int MAXV=100010;

struct Edge{
	int from;
	int to;
	int dis;
	Edge* next;
};

Edge E[MAXE];
Edge* head[MAXV];
Edge* top=E;

int v;
int e;
int otd[MAXV];
int ind[MAXV];
double dp[MAXV];
bool visited[MAXV];
std::queue<int> tpo;

void Insert(int,int,int);
void Initialize();
void DFS(int root);

int main(){
	Initialize();
	head[v]=NULL;
	dp[v]=0;
	DFS(1);
	while(!tpo.empty()){
		int top=tpo.front();
		tpo.pop();
		for(Edge* i=head[top];i!=0;i=i->next){
			dp[top]+=(double(i->dis)+dp[i->to])/double(otd[top]);
		}
	}
	printf("%.2lf\n",dp[1]);
	return 0;
}

void DFS(int root){
	visited[root]=true;
	for(Edge* i=head[root];i!=NULL;i=i->next){
		if(!visited[i->to])
			DFS(i->to);
	}
	tpo.push(root);
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("ldfrog.in","r",stdin);
	freopen("ldfrog.out","w",stdout);
#endif
	int from,to,dis;
	scanf("%d%d",&v,&e);
	for(int i=0;i<e;i++){
		scanf("%d%d%d",&from,&to,&dis);
		Insert(from,to,dis);
	}
}

inline void Insert(int from,int to,int dis){
	top->to=to;
	top->dis=dis;
	top->from=from;
	top->next=head[from];
	head[from]=top;
	otd[from]++;
	ind[to]++;
	top++;
}