时间限制: 1 s

 空间限制: 64000 KB

 题目等级 : 黄金 Gold

 查看运行结果

 

 

题目描述 

Description

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

　　给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。

　　到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。

　　现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入描述 

Input Description

　　第一行: 两个整数 N M，代表图中有N个点、M条边

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

输出描述 

Output Description

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

样例输入 

Sample Input

4 4

1 2 1

1 3 2

2 3 3

3 4 4

样例输出 

Sample Output

7.00

数据范围及提示 

Data Size & Hint

　　对于20%的数据   N<=100

　　对于40%的数据   N<=1000

　　对于60%的数据   N<=10000

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

 

来源：Nescafe 19

 

因为要无后效性，所以要拓扑排序。处理一个点之前，把它所有连向的点都处理完，所以拓扑排序要倒着来（我是直接反向建图）。

1 #include 
          
            2 #include 
           
             3 #include 
            
              4  5 using namespace std; 6  7 const int N(1100000+15); 8 queue
             
              que; 9 int n,m,u,v,w,rudu[N],chudu[N];10 double f[N];11 int head[N],edgesum;12 struct Edge13 {14     int from,to,next,dis;15     Edge(int from=0,int to=0,int next=0,int dis=0) :16         from(from),to(to),next(next),dis(dis) {}17 }edge[N];18 19 int ins(int from,int to,int dis)20 {21     edge[++edgesum]=Edge(from,to,head[from],dis);22     return head[from]=edgesum;23 }24 25 int main()26 {27     scanf("%d%d",&n,&m);28     for(int i=1;i<=m;i++)29     {30         scanf("%d%d%d",&u,&v,&w);31         chudu[u]++; rudu[u]++;32         ins(v,u,w);33     }34     for(int i=1;i<=n;i++)35         if(!rudu[i]) que.push(i);36     while(!que.empty())37     {38         u=que.front();39         que.pop();40         for(int i=head[u];i;i=edge[i].next)41         {42             v=edge[i].to;43             f[v]+=1.0*(f[u]+edge[i].dis)/chudu[v];44             rudu[v]--;45             if(!rudu[v]) que.push(v);46         }47     }48     printf("%.2lf",f[1]);49     return 0;50 }