c++ 记忆化递归

#include <cstring>
#include <iostream>
#include <iomanip>
using namespace std;

const int N=100005;
const int M=200005;

int head[N], dout[N];
int n, m, E=0;
double f[N];
struct{int v, ne, w;}e[M];
inline void add(int a, int b, int c){
    e[E].v=b;
    e[E].ne=head[a];
    e[E].w=c;
    head[a]=E++;
}

double dp(int u){
    if(f[u]>=0) return f[u];
    if(u==n) return f[u]=0;
    f[u]=0;
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        f[u]+=(e[i].w+dp(v))/dout[u];
    }
    return f[u];
}

int main(){
    memset(dout, 0x00, sizeof dout);
    memset(head, -1, sizeof head);
    cin>>n>>m;
    for(int i=0; i<m; ++i){
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c);
        dout[a]++; // 出度
    }
    memset(f, -1, sizeof f);
    cout<<fixed<<setprecision(2)<<dp(1)<<endl;
    return 0;
}