「Poetize3」绿豆蛙的归宿

描述 Description

给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

题解：
这种期望DP一般从终点开始倒推。
所以这道题既可以dfs，也可以写反向边的拓扑排序。
代码：

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<string>

#define inf 1000000000

#define maxn 200000

#define maxm 500+100

#define eps 1e-10

#define ll long long

#define pa pair<int,int>

#define for0(i,n) for(int i=0;i<=(n);i++)

#define for1(i,n) for(int i=1;i<=(n);i++)

#define for2(i,x,y) for(int i=(x);i<=(y);i++)

#define for3(i,x,y) for(int i=(x);i>=(y);i--)

#define mod 1000000007

using namespace std;

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=10*x+ch-'0';ch=getchar();}

    return x*f;

}
struct edge{int go,next,w;}e[2*maxn];
int n,m,head[maxn];
double f[maxn];
bool v[maxn];
void dfs(int x)
{
    if(v[x])return;v[x]=1;
    int cnt=0;
    for(int i=head[x],y;i;i=e[i].next)
    {
        cnt++;
        dfs(y=e[i].go);
        f[x]+=f[y]+e[i].w;
    }
    if(cnt)f[x]/=cnt;
}

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    n=read();m=read();
    for1(i,m)
     {
        int x=read();e[i].go=read();e[i].next=head[x];head[x]=i;e[i].w=read();
     }
    dfs(1);
    printf("%.2lf
",f[1]);

    return 0;

}