绿豆蛙的归宿
乍一看题，感觉像是一个$dp$
设$f[x]$表示从$x$号节点到终点的路径长度的期望值
那么最终答案就是$f[1]$
假设从$x$出发有$k$条边，那么
$$f[x]=\frac{1}{k}\sum\limits_{i=1}^{k}f[v_i]+w[i]$$
有一点需要注意的事情就是需要反着来递推，只要建一个反图就可以了
一道蓝题就这样水完了,淦

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=2e5+2020;
struct node
{
    int v,Next,w;
}e[N<<1];
int head[N],cnt;
int du[N],out[N];
void add(int u,int v,int w)
{
    e[++cnt].Next=head[u];
    head[u]=cnt;
    e[cnt].v=v;
    e[cnt].w=w;
}
double f[N];
int n,m;
queue<int> q;
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add(v,u,w);
        out[u]++,du[u]++;
    }
    f[n]=0;
    q.push(n);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].Next)
        {
            int to=e[i].v;
            f[to]+=(e[i].w+f[u])/du[to];
            out[to]--;
            if(out[to]==0) q.push(to);
        }
    }
    printf("%.2lf",f[1]);
    return 0;
}