绿豆蛙的归宿
对第i个点，f[i]表示i到终点的期望路径总长。
则f[n] = 0; 终点确定，则逆推。
对点x-->y
f[ x ] = sigema( f[ y ] w(x,y) )/out[ x ];
out[x]表示出度，把它变成入度就反向建图，为了拓扑。
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int M = 200500;
struct Edge{
int nxt,v;
double val;
};
Edge edge[M];
double in[M],dg[M];
double f[M];
int n,m,cnt,head[M];
void add(int u,int v,double w){
cnt ;
edge[cnt].v = v;
edge[cnt].val = w;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
int read(){
int x=0,dign=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-')dign=-1;
c = getchar();
}
while(c>='0'&&c<='9'){
x = x*10 c-'0';
c = getchar();
}
return x*dign;
}
void spfa(){
queue<int> q;
for(int i=1;i<=n;i )if(!in[i])q.push(i);
while(!q.empty()){
int u = q.front(); q.pop();
for(int v,i=head[u];i;i=edge[i].nxt){
double w = edge[i].val;
v = edge[i].v;
f[v] =(f[u] w)/dg[v];
in[v]--;
if(!in[v])q.push(v);
}
}
}
int main()
{
n = read(); m = read();
for(int i=0;i<m;i ){
int u,v;double w;
u = read(); v=read(); scanf("%lf",&w);
add(v,u,w);//反向建图
in[u] ; dg[u] ;
}
spfa();
printf("%.2lf",f[1]);
return 0;
}
