AT_abc192_e.[ABC192E] Train

在 AtCoder 国有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条铁路，编号为 $1$ 到 $M$。

第 $i$ 条铁路连接城市 $A_i$ 和城市 $B_i$，并且每当时刻为 $K_i$ 的倍数时，都会有列车分别从这两个城市发车前往对方。每趟列车从出发到到达需要 $T_i$ 的时间。

你现在位于城市 $X$。当你在时刻 $0$ 或之后，乘坐从城市 $X$ 出发的列车开始移动时，求你最早能到达城市 $Y$ 的时间。如果无法到达城市 $Y$，请报告这一情况。

另外，换乘所需时间可以忽略，因此在任意城市，只要你乘坐的列车到达时刻与另一趟列车的发车时刻相同，你就可以立即换乘。

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

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

输出你能到达城市 $Y$ 的最早时刻。如果无法到达城市 $Y$，则输出 $-1$。

限制条件

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

样例解释 1

首先，在时刻 $0$ 乘坐第 $1$ 条铁路，从城市 $1$ 前往城市 $2$，于时刻 $2$ 到达城市 $2$。随后，在时刻 $4$ 乘坐第 $2$ 条铁路，从城市 $2$ 前往城市 $3$，于时刻 $7$ 到达城市 $3$。没有比这更早到达城市 $3$ 的方法。

样例解释 2

首先，在时刻 $0$ 乘坐第 $2$ 条铁路，从城市 $3$ 前往城市 $2$，于时刻 $3$ 到达城市 $2$。随后，在时刻 $3$ 乘坐第 $1$ 条铁路，从城市 $2$ 前往城市 $1$，于时刻 $5$ 到达城市 $1$。

由 ChatGPT 4.1 翻译