空间跳跃 ### 题目描述 **题目背景** 在游戏《星际争霸 II》中，战列巡航舰作为人类的终极作战武器，在后期以及一些中期战术中发挥着空中堡垒的作用，其 "战术跳跃" 技能能让其在游戏中期在敌军基地上空造成打击之后在血量较低时撤离，进行无战损骚扰，在人类 vs 异虫对抗中经常用来压制异虫中期的发展。 **问题描述** 你在玩一个游戏，游戏中有 $n$ 个地点和 $m$ 条单向时空航道。每条时空航道形如$(u,v,w,x)$，其中 $u，v$ 表示这条时空航道的起点终点，$w$ 表示通过这条航道需要的时间（注意这个时间是现实当中游戏者的时间也是游戏内的时间），$x$ 表示这条航道使用的频繁程度。时空航道不会成环，但可能会有两条航道的起点相同同时终点也相同。游戏开始的时候，你的战列巡航舰到达了地点 1，每当你到达一个地点的时候，战舰的电脑会按照每个起点为该地点的时空航道的频繁程度随机选择一个航道并花费 w 单位时间到达该航道的终点。具体来说，对于一个时间点 $u$，假如有 $k$ 个起点为该地点的时空航道，他们的频繁程度分 别为 $x_1,x_2,x_3,···x_k$，那么选择第 $i$ 个航道的概率就是 $\frac{x_i}{\sum_{j=1}^{k}x_j}$。你的目的是在 $L$ 单位游戏时间内到达一个没有任何以该地点为起点的时空航道的地点。当然你可以在到达某一个地点时重新开始游戏，如果你重新开始这个游戏，你就能回到游戏开始的那一刻（即 1 号地点）并重置游戏内的时间（即你又可以有 $L$ 单位的时间去跳跃了），你也可以在没有任何以该地点为起点的地点重新开始，且无次数限制。你需要最小化你在现实中花费的时间。当然在你运气足够好的情况下，你一定可以达成游戏目标。 保证一定有至少一条以 1 号地点为起点的航道。 请阅读样例以更清晰地理解题意。 ### 输入描述 第一行三个正整数 $n，m，L$。 接下来 $m$ 行，每行四个正整数 $u，v，w，x$。 其中，$2 \leq n \leq 100，1 \leq m \leq 200，w,x \leq 100，0 \leq L \leq 10^9$， 保证输入的图无环，答案不超过 $10^9$。 ### 输出描述 一行一个浮点数表示答案，误差或者相对误差不超过 $10^{−9}$ 即为正确。 ### 输入输出样例 #### 示例 > 输入 ```txt 3 2 3 1 2 2 1 1 2 4 1 ``` > 输出 ```txt 6 ``` > 样例解释 设答案为 $Ans%。 则 $Ans = 1/2 \times 2 + 1/2 \times (Ans + 4)$。即有一半的可能性你可以直接完成游戏，否则你需要重新开始并再来一次。 解得 $Ans = 6\$。