UOJ Logo Zijian Online Judge

ZOJ

#50. 随机

Statistics

有一个有$n$个点和$m$条边的有向无环图。每条边形如$(u,v,w,x)$,其中$u$,$v$表示这条边的起点终点,$w$表示经过这条边花费的时间,$x$表示这条边的权重。图可能有重边。开始时你在$1$号点,每当你到达一个点的时候,你会按照该点出边的权重随机选一条边花费边对应的时间走过去。具体来说,对于一个点$u$,假如有$k$个起点为该点的边,它们的权重分别为$x_1,x_2,x_3...x_k$,那么选择第$i$个边的概率就是$\frac{x_i}{\sum_{j=1}^{k}x_j}$。你的目的是在$L$单位时间内到达一个出度为$0$的点。当然你可以在到达某一个点时重新开始,如果你重新开始,你就能回到$1$号点并重新开始(即从$0$时刻开始),且无次数限制。你需要最小化你的总时间,即包括重新开始之前花费的时间。当然在你运气足够好的情况下,你一定可以达成目标。保证一定有至少一条以$1$号地点为起点的边。请阅读样例以更清晰地理解题意。

输入格式

第一行三个正整数$n$,$m$,$L$。

接下来$m$行,每行四个正整数$u$,$v$,$w$,$x$。

输出格式

一行一个浮点数表示答案,令你的答案为$a$,标准答案为$b$,如果满足$\frac{|a-b|}{max(1,b)} \leq 10^{-9}$(即绝对误差或者相对误差不超过$10^{-9}$)即为正确。

样例一

input

3 2 3
1 2 2 1
1 2 4 1

output

6

explanation

设答案为$Ans$。

则$Ans=\frac{1}{2}\times 2+\frac{1}{2}\times(Ans+4)$。

即有一半的可能性你可以直接完成,否则你需要重新开始并再来一次。

解得$Ans=6$。

样例二

input

4 4 7
1 2 2 7
1 3 4 6
2 4 6 3
3 4 3 2

output

9.3333333333

样例三

input

5 7 12
1 3 5 5
4 5 7 9
2 5 8 1
3 5 4 4
1 2 3 3
3 4 3 1
2 4 2 5

output

11.3571428571

样例四

见下发文件

限制与约定

本题共有$25$个测试点,每个测试点$4$分。

对于全部数据$2\leq n\leq 100$,$1\leq m\leq 200$,$1\leq w,x\leq 100$,$0\leq L\leq 10^9$,保证输入的图无环,答案$\leq 10^9$,保证至少存在一条从$1$出发走到出度为$0$的点长度$\leq L$的路径。

具体数据规模请见下表。

测试点编号$n$$m$$w$特殊性质一特殊性质二
$1$$\leq 3$$\leq 3$$\leq 3$所有的边起点都为$1$号点
$2$$\le 100$
$3$$\leq 5$$\leq 4$$=1$
$4$
$5$$\leq 8$
$6$$\leq 100$
$7$$\leq20$$=n-1$$对于点u(2\leq u\leq n)有一条边(v,u)满足1\leq v\leq u-1$
$8$
$9$
$10$
$11$$\leq 100$
$12$
$13$
$14$$所有的边起点都为1号点$
$15$
$16$$=2$$\leq 200$$\leq 5$
$17$
$18$$\leq 100$
$19$$\leq 20$
$20$
$21$
$22$$\leq 100$
$23$
$24$
$25$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载