← 返回题目列表

AtCoder · abc192_e

E. 火车

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

分数: 500 点

问题陈述

在AtCoder共和国,有 N 城市编号 1 通过 N 和 M 铁路编号 1 通过 M.

铁路 i 连接城市 A_i 和城市 B_i 双向。时 0, K_i,以及所有后续的倍数 K_i,一列火车从这些城市中的每一个城市出发,前往另一个城市。每趟列车到达目的地所需的时间为 T_i.

您现在位于城市 X。查找您可以到达城市的最早时间 Y 当您乘坐从城市出发的火车开始旅程时 X 不早于时间 0。如果城市 Y 无法访问,请报告这一事实。
传输所需的时间可以忽略不计。也就是说,在每个城市,您都可以换乘与您的火车到达该城市的确切时间出发的火车。

约束

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1 \leq X,Y \leq N
  • X \neq Y
  • 1 \leq A_i,B_i \leq N
  • A_i \neq B_i
  • 1 \leq T_i \leq 10^9
  • 1 \leq K_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M X Y
A_1 B_1 T_1 K_1
\vdots
A_M B_M T_M K_M

输出

打印您可以到达城市的最早时间 Y。如果城市 Y 无法访问,打印 -1 代替。


示例输入 1

3 2 1 3
1 2 2 3
2 3 3 4

示例输出 1

7

首先,你乘坐铁路 1 时间 0 从城市出发 1 前往城市 2。您到达城市 2 时间 2.

然后,你乘坐铁路 2 时间 4 从城市出发 2 前往城市 3。您到达城市 3 时间 7.

没有办法到达城市 3 早些时候。


示例输入 2

3 2 3 1
1 2 2 3
2 3 3 4

示例输出 2

5

首先,你乘坐铁路 2 时间 0 从城市出发 3 前往城市 2。您到达城市 2 时间 3.

然后,你乘坐铁路 1 时间 3 从城市出发 2 前往城市 1。您到达城市 1 时间 5.


示例输入 3

3 0 3 1

示例输出 3

-1

示例输入 4

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

示例输出 4

26