配点 : 100 点
問題文
N 个机场,每个机场都有 它由数字 1 减去 N 表示。 有一个飞往
M 的航班。i 第 航班在机场 a_i 从机场出发 前往 b_i ,出发时间为 s_i ,到达时间为 t_i 。 您只能乘坐航班从一个机场前往另一个机场。假设转机时间可以忽略不计,即可以转乘与您当前航班同时起飞的另一个航班。
空港 1 从机场出发
求到 N 的行程时间,使行程时间尽可能短。然而,如果没有办法到达
请输出 -1 。这里,旅行时间是
您离开的时间 1 到达 S、空港 N 的时间
作为 T ,T - S 代表。
制約
- 2 \leq N \leq 200{,}000
- 0 \leq M \leq 200{,}000
- 1 \leq a_i, b_i \leq N
- 0 \leq s_i < t_i \leq 10^{9}
- a_i \ne b_i
- 所有输入均为整数
小課題
- ( 1 点) a_i = 1 如果 s_i = 0
- ( 99 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
N M a_1 b_1 s_1 t_1 a_2 b_2 s_2 t_2 \vdots a_M b_M s_M t_M
出力
空港 1 从机场出发
求到 N 减少前往目的地时的行程时间,使行程时间尽可能短。 1 行。然而,如果没有办法到达
从 -1 ,否则输出
入力例 1
3 3 1 3 0 5 1 2 3 4 2 3 6 7
出力例 1
4
時刻 3 出发的航班 2 ,航班 骑行时间 3 到达 7 。
这个测试用例不满足小课题1的否定。
入力例 2
2 0
出力例 2
-1
如果没有办法到达那里 -1 ,否则输出
这个测试用例满足小课题1的否定。
入力例 3
3 4 2 3 5 6 1 2 0 2 1 3 0 4 2 3 2 3
出力例 3
3
传输时间可以忽略不计。
这个测试用例满足小课题1的否定。