luogu#P1768. 天路

天路

题目描述

“那是一条神奇的天路诶 ~~~,把第一个神犇送上天堂 ~~~ ”,XDM 先生唱着这首“亲切”的歌曲,一道猥琐题目的灵感在脑中出现了。

和 C_SUNSHINE 大神商量后,这道猥琐的题目终于出现在本次试题上了,旨在难到一帮大脑不够灵活的 OIer 们(JOHNKRAM 真的不是说你……)。

言归正传,小 XX 的梦中,他在西藏开了一家大型旅游公司,现在,他要为西藏的各个景点设计一组铁路线。但是,小 XX 发现,来旅游的游客都很挑剔,他们乘火车在各个景点间游览,景点的趣味当然是不用说啦,关键是路上。试想,若是乘火车一圈转悠,却发现回到了游玩过的某个景点,花了一大堆钱却在路上看不到好的风景,那是有多么的恼火啊。

所以,小 XX 为所有的路径定义了两个值,ViV_iPiP_i,分别表示火车线路的风景趣味度和乘坐一次的价格。现在小 XX 想知道,乘客从任意一个景点开始坐火车走过的一条回路上所有的 VV 之和与 PP 之和的比值的最大值。以便为顾客们推荐一条环绕旅游路线(路线不一定包含所有的景点,但是不可以存在重复的火车路线)。

于是,小 XX 梦醒之后找到了你……

输入格式

第一行两个正整数 N,MN,M,表示有 NN 个景点,MM 条火车路线,火车路线是单向的。

以下 MM 行,每行 44 个正整数,分别表示一条路线的起点,终点,VV 值和 PP 值。

注意,两个顶点间可能有多条轨道,但一次只能走其中的一条。

输出格式

一个实数,表示一条回路上最大的比值,保留 11 位小数。

若没有回路,输出 1-1

5 6
1 2 1 1
4 1 6 2
5 4 8 1
2 3 2 2
5 2 4 1
3 5 6 4
2.3

提示

对于 30%30\% 的数据,1N1001 \le N \le 1001M201 \le M \le 20

对于 60%60\% 的数据,1N3,0001 \le N \le 3{,}0001M2,0001 \le M \le 2{,}000

对于 100%100\% 的数据,1N7,0001 \le N \le 7{,}0001M20,0001 \le M \le 20{,}0001Vi,Pi1,0001 \le V_i,P_i \le 1{,}000

保证答案在 200200 以内。