PID725 / 紧急追捕
题目描述

【背景描述】在你的帮助下,JC轻松地打败了DZY,夺回了他的GF。但是由于他的一时疏忽,他居然让邪恶的DZY逃走了。为了防止DZY再祸害其他人,他决定大公无私地把DZY抓回来!

【题目描述】DZY顺着交通网逃到了城市B,而JC还停留在原来的城市A,整个交通网有n个城市,城市A是第一个城市,城市B是第n个城市。某些城市之间有m条有向道路连接,JC每通过一条道路i都要花费一定的时间Ti和一定的金钱Wi。而对于一条JC从城市A到城市B的路径我们称之为一个方案,JC为了衡量一个方案的优劣定义了‘花费比’,任何一个方案的花费比为min(Σ(Wi*Ti)/Σ(Ti+Wi),min(Wi*n/Ti)),(注:i为方案中JC经过的道路,如果一条道路JC经过了p次,则在花费比计算式中就要累加p次)。但是JC是会魔法的,于是他想让自己的前行更快捷方便。JC最多可以使用k次加速魔法,即在经过一条道路i的时候可以将其Ti减半(向下取整)或者Wi加倍,这个效果只是瞬时有效,举例来说就是JC在经过道路i的时候发动了魔法,在下一次经过这个道路的时候这个魔法就失效了,如果要再保持效果就要再次使用魔法。而且对于同一条道路的同一时刻,JC不能同时发动多次魔法,即效果不能叠加!现在,JC想知道他从A到B可以得到的最小花费比是多少。

输入格式

第一行是三个正整数,n,m,k。接下来m行每行有4个整数描述一条道路i,分别为Fi,Ei,Ti,Wi,表示这条道路间接Fi到Ei,时间Ti,费用Wi。输入保证存在至少一条从A到B的路径。

输出格式

只输出一个实数表示最大价值比。保留两位小数。如果答案大于10^10则输出"are you mad?",大数据边权完全随机。

样例输入
样例输出
注释

【数据范围】对于30%的数据k=0,n<=5,m<=5

对于60%的数据k<=5,n<=500,m<=2000

对于100%的数据k<=20,n<=7000,m<=200000,边权为小于等于10^6的数

提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论