← 返回题目列表

AtCoder · oupc2023_day1_k

K. 最小化传输时间

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

配点 : 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. ( 1 点) a_i = 1 如果 s_i = 0
  2. ( 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的否定。