P4316 绿豆蛙的归宿

题意翻译

「Poetize3」

题目背景

随着新版百度空间的上线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

题目描述

给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入输出格式

输入格式：

第一行: 两个整数 N M，代表图中有N个点、M条边 第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边

输出格式：

从起点到终点路径总长度的期望值，四舍五入保留两位小数。

输入输出样例

输入样例#1：

4 4

1 2 1

1 3 2

2 3 3

3 4 4

输出样例#1：

7.00

说明

对于20%的数据 N<=100

对于40%的数据 N<=1000

对于60%的数据 N<=10000

对于100%的数据 N<=100000，M<=2*N

Solution：

　　设$f[i]$表示$i\rightarrow n$的期望距离，那么$f[u]=\frac{\sum\limits_{i=1}^{i\leq k}{(f[v_i]+w[u][v])}}{k}$，于是我们正着不方便求那就反向嘛！反向建图后就是一个简单的DAG递推了，拓扑排序一下就好了。

代码：

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int N=;

int n,m,to[N],net[N],w[N],h[N],cnt,rd[N],deg[N];

double f[N];

queue<int>q;

il int gi(){

    int a=;char x=getchar();

    while(x<''||x>'')x=getchar();

    while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();

    return a;

}

il void add(int u,int v,int c){rd[v]++,deg[v]++,to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;}

int main(){

    n=gi(),m=gi();

    int u,v,c;

    For(i,,m) u=gi(),v=gi(),c=gi(),add(v,u,c);

    q.push(n);

    while(!q.empty()){

        int u=q.front();q.pop();

        for(int i=h[u];i;i=net[i]){

            f[to[i]]+=(f[u]+w[i])/deg[to[i]];

            if(!--rd[to[i]]) q.push(to[i]);

        }

    }

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

    return ;

}