#include<bits/stdc++.h>
using namespace std;
double f[100010];
vector<pair<int,int>>G[100010];
void dfs(int x)
{
	if(f[x])return;
	for(auto i:G[x])//遍历向下走
	{
		int y=i.first,w=i.second;
		dfs(y);
		f[x]+=(f[y]+w)*1.0/G[x].size();
    //计算走到x点的概率,当前点的长度除以siz[x]
	}
}//纸张递归
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,x,y,c;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		G[x].push_back({y,c});//建图
	}
	memset(f,0,sizeof f);
	dfs(1);//从起点开始
	printf("%.2lf\n",f[1]);
	return 0;
}
  

阎帝的代码 从1到n一步一步的走,siz[x]表示x可以走的路的总数,f[x]表示x往下走的期望长度,概率DP即可

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<pair<int,int> >G[N];
double f[N];
int n,m,siz[N];
void dfs(int x,int xfa)
{
	if(f[x])return ;
	for(auto i:G[x])
	{
		dfs(i.first,x);
		f[x]+=1.0*(f[i.first]+i.second)/siz[x];
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,w;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&w);
		G[x].push_back({y,w});
		siz[x]++;
	}
	dfs(1,0);
	printf("%.2lf\n",f[1]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,rd[100010];
struct N{
	ll y,v;
};
vector<N> e[100010];
double f[100010],g[100010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1,x,y,v;i<=m;i++){
		cin>>x>>y>>v;
		e[x].push_back({y,v});
		rd[y]++;
	}
	queue<int> q;
	q.push(1);
	g[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		f[x]/=g[x];
		for(N i:e[x]){
			int y=i.y,v=i.v;
			f[y]+=(f[x]+v)/e[x].size()*g[x];
			g[y]+=1.0/e[x].size()*g[x];
			rd[y]--;
			if(!rd[y])q.push(y);
		}
	}
	printf("%.2lf",f[n]);
	return 0;
}

E41 概率DP 求期望 拓扑排序

#include<bits/stdc++.h>//高斯消元版，只能处理N<=1000，本题只过2个点
using namespace std;
const int N=1100,M=220000;
const double eps=1e-8;
struct edge{int x,y,c,pre;}e[M];int elen,last[N];
void add(int x,int y,int c){elen++;e[elen]={x,y,c,last[x]};last[x]=elen;}
int n,m, d[N],X[M],Y[M];
double a[N][N],f[N],g[M];
void gauss() 
{
	for(int i=1;i<n;i++)//第i主元
	{
		for(int k=i;k<n;k++)if(fabs(a[k][i])>eps) {swap(a[k],a[i]);break;}//换非0行
		for(int k=1;k<n;k++)if(k!=i)//对角化
		{
			double bs=a[k][i]/a[i][i];//第k行的系数是第i行的倍数 
			for(int j=1;j<=n;j++)a[k][j]-=bs*a[i][j];
		}
	}
	for(int i=1;i<n;i++) f[i]=a[i][n]/a[i][i];//除以主元
}
int main()
{
    scanf("%d%d",&n,&m);
    elen=0;memset(last,0,sizeof last);
    memset(d,0,sizeof d);
    for(int i=1,x,y,c;i<=m;i++)
    {
    	scanf("%d%d%d",&x,&y,&c);
    	add(x,y,c);
    	d[x]++;
    }
    memset(a,0,sizeof a);memset(f,0,sizeof f);
    for(int x=1;x<n;x++)//构造增广矩阵
    {
    	for(int k=last[x];k;k=e[k].pre)
    	{
    		int y=e[k].y;
    		if(y!=n)a[y][x]=-1.0/d[x]; 
    	}
    	a[x][x]=1;
    }
    a[1][n]=1;
    gauss();//点的期望次数
    for(int i=1;i<=m;i++)g[i]=f[e[i].x]/d[e[i].x];//边的期望次数

    double ans=0;
    for(int i=1;i<=m;i++) ans+=g[i]*e[i].c;
    printf("%.2lf",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110000,M=210000;
struct edge{int x,y,c,pre;}a[M];int alen,last[N],out[N];
double f[N];
void add(int x,int y,int c)
{
	alen++;a[alen]=edge{x,y,c,last[x]};last[x]=alen;out[x]++;
}
void dfs(int x)
{
if(f[x])return ;
for(int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
dfs(y);
f[x]+=(f[y]+a[k].c)*1.0/out[x];
}
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
alen=0;memset(last,0,sizeof last);memset(out,0,sizeof out);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);add(x,y,c);
}
memset(f,0,sizeof f );
dfs(1);
printf("%.2lf\n",f[1]);
return 0;
}