← 返回题目列表

AtCoder · abc324_f

I. 美丽的道路

中文机器翻译题面 查看原题

分数: 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