链接：

#include <stdio.h>

int main()

{

    puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢");

    puts("网址：blog.csdn.net/vmurder/article/details/46467217");

}

题解：

呃。拓扑图上从后往前扫就好了Qwq

代码：

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 101000

using namespace std;

struct Eli

{

    int v,l,n;

    bool f;

}e[N<<1];

int head[N],cnt,d[N],D[N];

inline void add(int u,int v,int l)

{

    e[++cnt].v=v;

    e[cnt].l=l;

    e[cnt].n=head[u];

    head[u]=cnt;

}

double f[N];

queue<int>q;

bool vis[N];

int n,m;

void bfs()

{

    int i,u,v;

    q.push(n);

    while(!q.empty())

    {

        vis[u=q.front()]=true,q.pop();

        for(i=head[u];i;i=e[i].n)

            if(!vis[v=e[i].v])q.push(v);

    }

}

int main()

{

    int i,u,v;

    int a,b,c;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)

    {

        scanf("%d%d%d",&a,&b,&c);

        add(b,a,c),d[a]++;

    }

    for(i=1;i<=n;i++)D[i]=d[i]?d[i]:1;

    bfs();

    q.push(n);

    while(!q.empty())

    {

        u=q.front(),q.pop(),f[u]/=D[u];

        for(i=head[u];i;i=e[i].n)

        {

            if(vis[u])f[v=e[i].v]+=f[u]+e[i].l;

            if(--d[v]==0)q.push(v);

        }

    }

    printf("%.2lf\n",f[1]);

    return 0;

}