/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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 を出力してください。
制約
- 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
出力
高橋君が都市 N に到達することができる最も早い時刻を整数で出力せよ。ただし、都市 N に到達できないときはかわりに -1 を出力せよ。
入力例 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 に到着することができます。
時刻 4 より早く都市 2 に到着することはできません。
入力例 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
都市 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
Score : 500 points
Problem Statement
The Republic of AtCoder has N cities and M roads.
The cities are numbered 1 through N, and the roads are numbered 1 through M. Road i connects City A_i and City B_i bidirectionally.
There is a rush hour in the country that peaks at time 0. If you start going through Road i at time t, it will take C_i+ \left\lfloor \frac{D_i}{t+1} \right\rfloor time units to reach the other end. (\lfloor x\rfloor denotes the largest integer not exceeding x.)
Takahashi is planning to depart City 1 at time 0 or some integer time later and head to City N.
Print the earliest time when Takahashi can reach City N if he can stay in each city for an integer number of time units. It can be proved that the answer is an integer under the Constraints of this problem.
If City N is unreachable, print -1 instead.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 C_1 D_1 \vdots A_M B_M C_M D_M
Output
Print an integer representing the earliest time when Takahashi can reach City N, or -1 if City N is unreachable.
Sample Input 1
2 1 1 2 2 3
Sample Output 1
4
We will first stay in City 1 until time 1. Then, at time 1, we will start going through Road 1, which will take 2+\left\lfloor \frac{3}{1+1} \right\rfloor = 3 time units before reaching City 2 at time 4.
It is impossible to reach City 2 earlier than time 4.
Sample Input 2
2 3 1 2 2 3 1 2 2 1 1 1 1 1
Sample Output 2
3
There may be multiple roads connecting the same pair of cities, and a road going from a city to the same city.
Sample Input 3
4 2 1 2 3 4 3 4 5 6
Sample Output 3
-1
There may be no path from City 1 to City N.
Sample Input 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
Sample Output 4
20