【题意】给定DAG带边权连通图，保证所有点都能到达终点n，每个点等概率沿边走，求起点1到终点n的期望长度。n<=10^5。
【算法】期望DP
【题解】f[i]表示到终点n的期望长度。
f[n]=0
f[i]=(f[j]+e[i].w)/k[i]，i-->j，k[i]是i的出度。
因为是点x等概率出发，所以一定要从x算，不能倒着来。
原理：【专题】概率和期望
考虑到深搜的爆栈风险，写了拓扑排序+期望DP
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
int first[maxn],n,m,in[maxn],a[maxn],tot=,k[maxn],cnt=;//////////////////////
double f[maxn];
queue<int>q;
struct edge{int v,w,from;}e[maxn*];
void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;in[v]++;k[u]++;}
int main(){
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
}
for(int i=;i<=n;i++)if(!in[i])q.push(i);
while(!q.empty()){
a[++cnt]=q.front();q.pop();
for(int i=first[a[cnt]];i;i=e[i].from){
in[e[i].v]--;
if(!in[e[i].v])q.push(e[i].v);
}
}
for(int j=n;j>=;j--){
int x=a[j];
for(int i=first[x];i;i=e[i].from){
f[x]+=f[e[i].v]+e[i].w;
}
if(k[x])f[x]/=k[x];
}
printf("%.2lf",f[]);
return ;
}
有边表的tot时，一定要注意不要用变量tot。