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$。

输入输出样例 #1

输入 #1

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

输出 #1

7

输入输出样例 #2

输入 #2

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

输出 #2

5

输入输出样例 #3

输入 #3

3 0 3 1

输出 #3

-1

输入输出样例 #4

输入 #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

说明/提示

限制条件

• $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 翻译