分数: 500 点
问题陈述
有一个有向图 N 顶点和 M 边缘。每条边都有两个正整数值: 美女 和 成本 树的.
对于 i = 1, 2, \ldots, M, i第一条边从顶点定向 u_i 到顶点 v_i,有美感 b_i 和成本 c_i。 这里,约束保证 u_i \lt v_i.
查找路径的以下最大值 P 从顶点 1 到顶点 N.
- 所有边缘的整体美感 P 除以所有边的总成本 P.
这里,约束保证给定图至少有一条从顶点出发的路径 1 到顶点 N.
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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}.
示例输入 1
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
示例输出 1
0.7500000000000000
对于路径 P 通过 2-nd, 6-th,和 7按此顺序的第条边并访问顶点 1 \rightarrow 3 \rightarrow 4 \rightarrow 5,所有边缘的整体美感 P 除以所有边的总成本 P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75,这是最大可能值。
示例输入 2
3 3 1 3 1 1 1 3 2 1 1 3 3 1
示例输出 2
3.0000000000000000
示例输入 3
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
示例输出 3
1.8333333333333333