AT_abc204_e [ABC204E] Rush Hour 2

题目描述

AtCoder 国有 $N$ 个城市和 $M$ 条道路。

城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，且为双向道路。

AtCoder 国存在以时刻 $0$ 为高峰的“高峰时段”。如果在时刻 $t$ 开始通过第 $i$ 条道路，则需要花费 $C_i + \left\lfloor \frac{D_i}{t+1} \right\rfloor$ 的时间才能通过（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。

高桥君可以在时刻 $0$ 或之后的整数时刻从城市 $1$ 出发，通过道路前往城市 $N$。

高桥君可以在每个城市等待整数时间。请输出高桥君能够到达城市 $N$ 的最早时刻。如果无法到达城市 $N$，则输出 $-1$。

已知在题目限制下，答案一定为整数。

输入格式

输入以以下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$ $C_1$ $D_1$
$\vdots$
$A_M$ $B_M$ $C_M$ $D_M$

输出格式

输出高桥君能够到达城市 $N$ 的最早时刻。如果无法到达城市 $N$，则输出 $-1$。

输入输出样例 #1

输入 #1

2 1
1 2 2 3

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

3

输入输出样例 #3

输入 #3

4 2
1 2 3 4
3 4 5 6

输出 #3

-1

输入输出样例 #4

输入 #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

说明/提示

限制条件

• $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$
• 输入均为整数

样例解释 1

首先在城市 $1$ 等待到时刻 $1$。然后在时刻 $1$ 通过第 $1$ 条道路移动，所需时间为 $2+\left\lfloor \frac{3}{1+1} \right\rfloor = 3$，因此在时刻 $4$ 到达城市 $2$。无法更早到达城市 $2$。

样例解释 2

可能存在多条道路连接同一对城市，或存在连接同一城市的自环道路。

样例解释 3

也可能不存在从城市 $1$ 到城市 $N$ 的路径。

由 ChatGPT 4.1 翻译