分数: 500 点
问题陈述
AtCoder 共和国有 N 城市和 M 道路。
城市已编号 1 通过 N,并且道路已编号 1 通过 M。道路 i 连接城市 A_i 和城市 B_i 双向。
全国有上下班高峰时间 0。如果你开始走这条路 i 时间 t,需要 C_i+ \left\lfloor \frac{D_i}{t+1} \right\rfloor 时间单位到达另一端。 (\lfloor x\rfloor 表示不超过的最大整数 x.)
高桥正计划离开城市 1 时间 0 或一些 整数时间 稍后前往市区 N.
打印高桥最早能到达 City 的时间 N 如果他能在每个城市停留一段时间 整数个时间单位。可以证明,在该问题的约束条件下,答案是一个整数。
如果城市 N 无法访问,打印 -1 代替。
约束
- 2 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 1 \leq A_i,B_i \leq N
- 0 \leq C_i,D_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 D_1 \vdots A_M B_M C_M D_M
输出
打印一个整数,表示 Takahashi 可以到达 City 的最早时间 N,或 -1 如果城市 N 无法访问。
示例输入 1
2 1 1 2 2 3
示例输出 1
4
我们将首先留在城市 1 直到时间 1。然后,在某个时间 1,我们将开始穿过公路 1,这将需要 2+\left\lfloor \frac{3}{1+1} \right\rfloor = 3 到达城市之前的时间单位 2 时间 4.
无法到达城市 2 早于时间 4.
示例输入 2
2 3 1 2 2 3 1 2 2 1 1 1 1 1
示例输出 2
3
可能有多条道路连接同一对城市,以及从一个城市到同一城市的道路。
示例输入 3
4 2 1 2 3 4 3 4 5 6
示例输出 3
-1
可能没有从 City 出发的路径 1 前往城市 N.
示例输入 4
6 9 1 1 0 0 1 3 1 2 1 5 2 3 5 2 16 5 2 6 1 10 3 4 3 4 3 5 3 10 5 6 1 100 4 2 0 110
示例输出 4
20