记录编号	425394	评测结果	AAAAAAAAAA
题目名称	[Nescafe19] 绿豆蛙的归宿	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2017-07-15 09:52:05	内存使用	1.96 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=100000+10;
int n,m,num;
int head[M],from[M];
double f[2*M];
struct DATE{
	int to,w,last;
}date[2*M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y,int z){
	date[++num]=(DATE){y,z,head[x]};
	head[x]=num;
}
void dfs(int x){
	if(x==n) return ;
	/*for(int i=head[x];i;i=date[i].last){
		int to=date[i].to;
		dfs(to);
	}*/
	f[x]=0;
	for(int i=head[x];i;i=date[i].last){
		int to=date[i].to;
		dfs(to);
		f[x]+=(f[to]+date[i].w)/(double)(from[x]);
	}
}
int DK(){
	freopen("ldfrog.in","r",stdin);
	freopen("ldfrog.out","w",stdout);
	n=read();m=read();
	int aa,bb,cc;
	for(int i=1;i<=m;i++){
		aa=read();bb=read();cc=read();
		from[aa]++;
		add(aa,bb,cc);
	}
	dfs(1);
	printf("%.2lf",f[1]);
	return 0;
}
int dk=DK();
int main(){
	;
}