$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

$f_i\ 表示从\ i\ 号点走到\ n\ 号点的期望值$

$状态转移：f_i=\sum\limits_{}\dfrac{1}{k}(f_j+w_{ij})$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = N * 2;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dout[N];
double f[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

double dp(int u)
{
    f[u]=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        f[u]+=(dp(j)+w[i])/dout[u];
    }
    return f[u];
}

int main()
{
    scanf("%d%d",&n,&m);

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        dout[a]++;
    }

    memset(f,-1,sizeof f);

    printf("%.2lf\n",dp(1));

    return 0;
}