期望的线性性质:E(ax+by)=aE(X)+bE(Y)

1-n总长度的期望

到达某个结果的期望值 = 这个结果 * 从起始状态到这个状态的概率
f[i]=∑1/k*(w[i]+f(S[i])
f[i]表示从i走到n的期望 边界f(N)=0即n到n的期望是0 答案为f[1]
没有权值 ： p(x)=p1x1+p2x2+....+pnxn
有权值： p(y)=（p1(x1+w)+p2(x2+w)+…+pn(xn+w)）/n
从x走到y： E(y)=E(x)+∑pi∗wi

#include <iostream>
#include <cstring>

using namespace std;

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

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

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

double dp(int u)//记忆化搜索
{
    if(f[u] >= 0) return f[u];//如果见过
    f[u] = 0;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        f[u] += (w[i] + dp(j)) / d[u];//d表示出边多少  dp(j)这里使用了倒推
    }
    return f[u];
}


int main()
{
    cin >> n >> m;
    memset(h , -1 , sizeof h);

    while(m--)
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c);
        d[a]++;//出度++
    }

    memset(f , -1 , sizeof f);//初始化成一个不存在的数

    printf("%.2lf\n" , dp(1));//从1开始
    return 0;
}