BZOJ-3036: 绿豆蛙的归宿

Description

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

被自己蠢哭，循环边又写成了n。dp[i]表示第i个点到n的期望复杂度。然后拓扑转移就好了。（dfs好像也行）

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int head[110000],to[210000],nxt[210000],data[210000],cnt;
inline void add(int x,int y,int z)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
    data[cnt]=z;
}
int cd[110000],chu[110000];
double dp[110000];
void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(!cd[i]) q.push(i);
    int x;
    while(!q.empty())
    {
        x=q.front(); q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            dp[to[i]]+=(dp[x]+data[i])*1.0/chu[to[i]];
            cd[to[i]]--;
            if(!cd[to[i]]) q.push(to[i]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        cd[x]++; add(y,x,z);
    }
    for(int i=1;i<=n;i++) chu[i]=cd[i];
    topsort();
    printf("%.2lf\n",dp[1]);
    return 0;
}