AcWing 217. 绿豆蛙的归宿

正推概率，逆推期望
\(f[i]\)表示从\(i\)到\(N\)的概率
递推方程：\(f[i] = \sum (\frac{1}{k} \times (w[i] + f[j]))\)

#include 
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int T, n, m;
int h[N], e[M], ne[M], w[M], idx;
int dout[N];
double f[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 != -1; i = ne[i]) {
        int j = e[i];
        f[u] += (w[i] + dp(j)) / dout[u];
    }
    return f[u];
}
int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(f, -1, sizeof f);
    for (int i = 1; i <= m; i ++ ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        dout[a] ++;
    }
    printf("%.2lf\n", dp(1));
    return 0;
}