记录编号	414994	评测结果	AAAAAAAAAA
题目名称	[Nescafe19] 绿豆蛙的归宿	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.173 s
提交时间	2017-06-15 15:21:26	内存使用	3.41 MiB

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 201000
using namespace std;
int n,m;
struct qian
{
       int next,to,w;
}edge[N];
int head[N],cnt=1;
void add(int u,int v,int w)
{
     edge[cnt].w=w;
     edge[cnt].to=v;
     edge[cnt].next=head[u];
     head[u]=cnt++;
}
double p=1;
double ans;
double len;
int flag[N];
double out[N];
void dfs(int x)
{
     if(x==n)
     {
           ans+=p*len;
           return;  
     }
     for(int i=head[x];i;i=edge[i].next)
     {
        int to=edge[i].to;
        if(flag[to]==0)
        {
           flag[to]=1;
           len+=edge[i].w;
           p/=out[x];
           //cout<<"x="<<x<<"   to="<<to<<"  len="<<len<<"  p="<<p<<"  out[x]="<<out[x]<<endl;
           dfs(to);
           flag[to]=0;
           len-=edge[i].w;
           p=p*out[x];;
        }
        
     }
}
int haha()
{
    freopen("ldfrog.in","r",stdin);
    freopen("ldfrog.out","w",stdout); 
    scanf("%d%d",&n,&m);
    pos(i,1,m)
    {
       int x,y,z;
       scanf("%d%d%d",&x,&y,&z);
       add(x,y,z);
       out[x]++;
    }
    dfs(1);
    printf("%0.2lf",ans);
    //while(1);
    return 0;
}
int sb=haha();
int main()
{;
}