← 返回题目列表

AtCoder · abc204_e

E. 尖峰时刻2

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

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