记忆化搜索（dfs+memo）无环有向图

这是一道可以当作板子的极简记忆化搜索 

建立a 是邻接表，其中 a[x] 存储从节点 x 出发能到达的所有节点。

b[x] 记录从节点 x 出发的所有边的权重之和。根据数学原理，我们很容易发现，一个根（起点）的期望，等于他所有子的期望加上边权和，除边

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, x, y, z;
vector<vector<int>> a(N); //邻接表
double b[N]; //记录从节点 x 出发的所有边的权重之和。

double dfs(int x) {
    if (x == n) return 0.0; //到达终点，期望为0

    double o = 0.0;
    int p = a[x].size();
    for (auto i : a[x]) {//所有子的期望和
        o += dfs(i);
    }
    o += b[x];//加上边权和
    return o / p;//期望
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y >> z;
        a[x].push_back(y);
        b[x] += z;
    }
    double o = dfs(1);
    printf("%.2lf\n", o); 
    return 0;
}

这样写出来，思路是对的，但是在多条路径下，我们明显可以发现，每个子节点都会计算很多次，所以我们使用记忆化来优化；

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, x, y, z;
vector<vector<int>> a(N); 
double b[N]; 
double memo[N];  //储存
bool vis[N]; //判断是否被计算过

double dfs(int x) {
    if (vis[x]) return memo[x];//如果计算了，直接返回结果
    if (x == n) return 0.0; 
    vis[x] = true;
    double o = 0.0;
    int p = a[x].size();
    for (auto i : a[x]) {
        o += dfs(i);
    }
    if (p == 0) return 0.0;  
    o += b[x];
    return memo[x]=o / p;//返回时给memo记录
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y >> z;
        a[x].push_back(y);
        b[x] += z;
    }
    memset(vis, false, sizeof(vis));//初始化
    double o = dfs(1);
    printf("%.2lf\n", o); 
    return 0;
}