P4316 绿豆蛙的归宿 ( 拓扑 + 期望dp

#include 
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using ll = long long;
struct edge{
    int from,to,val;
    int next;
}g[200010];
int head[200010];
 
 
int n,m;
int idx = 0;
void add(int u, int v , int val){
    idx++;
    g[idx].from = u;
    g[idx].to = v;
    g[idx].val = val;
    g[idx].next = head[u];
    head[u] = idx;
}
int siz[200010];
int in[200010];
double dp[200010];//每个点到终点的期望路径长
//dp[n] = 0;
//从已知的最终状态向前转移
//跑拓扑
//每个点走到 终点的期望 dp[i] = (dp[to] + val) / k
int main(){
    cin>>n>>m;
    for(int i = 1 ; i <= m ; i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(b,a,c);
        in[a] ++;
        siz[a] ++;
    }
 
    //memset(dp , 126 , sizeof dp);
    dp[n] =  0;
    queue<int> q;
    q.push(n);
    while(q.size()){
        auto x = q.front();
        q.pop();
        //cout<
        for(int i = head[x] ; i ; i = g[i].next){
            int to = g[i].to;
            int val = g[i].val;
            //cout<
            in[to]--;
            dp[to] += val + dp[x];
            if(in[to] == 0){
                q.push(to);
                dp[to] /= siz[to];
            }
 
        }
 
    }
 
    printf("%.2lf" , dp[1]);
}   
 
 

期望dp的 常规设法 ， 很有可能是从已知的最终态期望 去 反推需要的期望