Train

题目描述

在 AtCoder 共和国，有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条铁路，编号为 $1$ 到 $M$。 铁路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$。在时间 $0$、$K_i$ 以及之后所有 $K_i$ 的倍数时刻，会有一列火车从这两个城市出发并前往另一个城市。这些列车到达目的地所需的时间为 $T_i$。 你现在在城市 $X$。当你从城市 $X$ 乘坐一列不早于时间 $0$ 出发的火车开始旅程时，求到达城市 $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$。

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

7

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

5

3 0 3 1

-1

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

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$ 输入中的所有数值都是整数。首先，你在时间 $0$ 乘坐铁路 $1$ 从城市 $1$ 到城市 $2$。你在时间 $2$ 抵达城市 $2$。 然后，你在时间 $4$ 乘坐铁路 $2$ 从城市 $2$ 到城市 $3$。你在时间 $7$ 抵达城市 $3$。 无法更早到达城市 $3$。
首先，你在时间 $0$ 乘坐铁路 $2$ 从城市 $3$ 到城市 $2$。你在时间 $3$ 抵达城市 $2$。 然后，你在时间 $3$ 乘坐铁路 $1$ 从城市 $2$ 到城市 $1$。你在时间 $5$ 抵达城市 $1$。

标签: AtCoder|abc192E

来源

AtCoder|abc192E