优美路径

题目描述

有一个具有 $N$ 个顶点和 $M$ 条边的有向图。每条边都有两个正整数属性：beauty（美丽度）和 cost（花费）。

对于 $i = 1, 2, \ldots, M$，第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$，美丽度为 $b_i$，花费为 $c_i$。 这里，约束保证 $u_i \lt v_i$。

对于一条从顶点 $1$ 到顶点 $N$ 的路径 $P$，求下面这个式子的最大值：

$P$ 上所有边的美丽度之和除以 $P$ 上所有边的花费之和。

这里，约束保证给定的图至少存在一条从顶点 $1$ 到顶点 $N$ 的路径。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$u_1$ $v_1$ $b_1$ $c_1$
$u_2$ $v_2$ $b_2$ $c_2$
$\vdots$
$u_M$ $v_M$ $b_M$ $c_M$

输出格式

输出答案。当你的输出与真实答案的相对误差或绝对误差不超过 $10^{-9}$ 时，你的输出会被判为正确。

样例

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

0.7500000000000000

对于依次经过第 $2$、第 $6$、第 $7$ 条边、访问顶点 $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 的路径 $P$，$P$ 上所有边的美丽度之和除以所有边的花费之和为 $(b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75$，这是最大值。

3 3
1 3 1 1
1 3 2 1
1 3 3 1

3.0000000000000000

10 20
3 4 1 2
7 9 4 5
2 4 4 5
4 5 1 4
6 9 4 1
9 10 3 2
6 10 5 5
5 6 1 2
5 6 5 2
2 3 2 3
6 10 4 4
4 6 3 4
4 8 4 1
3 5 3 2
2 4 3 2
3 5 4 2
1 5 3 4
1 2 4 2
3 7 2 2
7 8 1 3

1.8333333333333333

数据范围

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq u_i \lt v_i\leq N$
• $1\leq b_i, c_i\leq 10^4$
• 存在一条从顶点 $1$ 到顶点 $N$ 的路径。
• 输入中的所有数值均为整数。