2312 问题 N: 蓝桥杯2019年第十届省赛真题-空间跳跃

时间限制: 1s 内存限制: 128MB 提交: 63 解决: 0
题目描述

在游戏《星际争霸 II》中,战列巡航舰作为人类的终极作战武器,在后期 以及一些中期战术中发挥着空中堡垒的作用,其 “战术跳跃” 技能能让其在游戏 中期在敌军基地上空造成打击之后在血量较低时撤离,进行无战损骚扰,在人 类 vs 异虫对抗中经常用来压制异虫中期的发展。

你在玩一个游戏,游戏中有 n 个地点和 m 条单向时空航道。每条时空航道形如 (u, v, w, x),其中 u,v 表示这条时空航道的起点终点,w 表示通过这条航道需要的时间(注意这个时间是现实当中游戏者的时间也是游戏内的时间),x表示这条航道使用的频繁程度。时空航道不会成环,但可能会有两条航道的起别为x ,x ,x ,···x,那么选择第i个航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj点相同同时终点也相同。游戏开始的时候,你的战列巡航舰到达了地点 1,每当你到达一个地点的时候,战舰的电脑会按照每个起点为该地点的时空航道的频繁程度随机选择一个航道并花费 w 单位时间到达该航道的终点。具体来说,对于一个时间点 u,假如有 k 个起点为该地点的时空航道,他们的频繁程度分别为x ,x ,x ,···x,那么选择第i个航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj单位游戏时间内到达一个没有任何以该地点为起点的时空航道的地点。当然你 可以在到达某一个地点时重新开始游戏,如果你重新开始这个游戏,你就能回 到游戏开始的那一刻(即 1 号地点)并重置游戏内的时间(即你又可以有 L 单 位的时间去跳跃了),你也可以在没有任何以该地点为起点的地点重新开始,且 无次数限制。你需要最小化你在现实中花费的时间。当然在你运气足够好的情 况下,你一定可以达成游戏目标。

保证一定有至少一条以 1 号地点为起点的航道。 请阅读样例以更清晰地理解题意。

输入

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

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

(2 ≤ n ≤ 100,1 ≤ m ≤ 200,w, x ≤ 100,0 ≤ L ≤ 109)

输出

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

样例输入
3 2 3 
1 2 2 1 
1 2 4 1
样例输出
6
提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

比赛公告

全部蓝桥杯真题,模拟训练,博客发布完整题解的同学有奖励哦!


预告:四月月赛为女生专场,赶紧预约你的女神! C语言网只能帮单身的你帮到这了!