题目链接：戳我
感觉挺简单的。就是一个简单的DAG上的期望问题。
暴力的话是把所有的路径都算出来，长度加一起再除以总路径数量。然后优化就是利用期望的线性性（可加性），我们把每条边的期望算出来，然后再相加就可以了。
显然求期望=概率*边长。我们可以考虑先把每个点经过的概率算出来，然后再往边上转移。因为是DAG，所以我们直接上拓扑排序就可以了。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define MAXN 200010
using namespace std;
int n,m,t,cnt;
int head[MAXN],chu[MAXN],id[MAXN],w[MAXN],ru[MAXN];
double ans;
double val[MAXN],node[MAXN];
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
vector<int>vec[MAXN];
inline void add(int from,int to,int dis){edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;}
inline void init()
{
queue<int>q;
q.push(1);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].nxt)
{
node[edge[i].to]+=node[x]/chu[x];
ru[edge[i].to]--;
if(ru[edge[i].to]==0) q.push(edge[i].to);
}
}
}
inline void solve(int x)
{
for(int i=1;i<=n;i++)
for(int j=0;j<vec[i].size();j++)
val[vec[i][j]]+=node[i]/chu[i];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d%d",&u,&v,&w[i]);
add(u,v,w[i]);
chu[u]++,ru[v]++;
vec[u].push_back(i);
}
node[1]=1.0;
init();
solve(1);
for(int i=1;i<=m;i++) ans+=1.0*w[i]*val[i];
printf("%.2lf
",ans);
}