Description
随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。
给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
Input
第一行: 两个整数 N M，代表图中有N个点、M条边
第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边
Output
从起点到终点路径总长度的期望值，四舍五入保留两位小数。
拓扑排序后逆序dp，f[i]表示从i走到n的期望路径长度
#include<cstdio>
const int N=,M=,R=;
int n,m;
int et[M],ev[M],enx[M],e0[N],ep=;
int in[N];
int q[N],ql=,qr=;
double f[N];
char buf[R],*ptr=buf-;
inline int _int(){
int x=,c=*++ptr;
while(c>||c<)c=*++ptr;
while(c>&&c<)x=x*+c-,c=*++ptr;
return x;
}
int main(){
fread(buf,,R-,stdin);
n=_int();m=_int();
for(int i=;i<m;++i){
int a=_int(),b=_int(),c=_int();
et[ep]=b;enx[ep]=e0[a];ev[ep]=c;e0[a]=ep++;
++in[b];
}
q[qr++]=;
while(ql!=qr){
int w=q[ql++];
for(int i=e0[w];i;i=enx[i]){
int u=et[i];
if(!--in[u])q[qr++]=u;
}
}
f[n]=;
for(int p=qr-;~p;--p){
int w=q[p],o=;
for(int i=e0[w];i;i=enx[i]){
int u=et[i];
++o;
f[w]+=f[u]+ev[i];
}
f[w]/=o;
}
printf("%.2f\n",f[]);
return ;
}