101924: [AtCoder]ABC192 E - Train

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $500$ points

Problem Statement

In the Republic of AtCoder, there are $N$ cities numbered $1$ through $N$ and $M$ railroads numbered $1$ through $M$.

Railroad $i$ connects City $A_i$ and City $B_i$ bidirectionally. At time $0$, $K_i$, and all subsequent multiples of $K_i$, a train departs from each of these cities and head to the other city. The time each of these trains takes to reach the destination is $T_i$.

You are now at City $X$. Find the earliest time you can reach City $Y$ when you start the journey by taking a train that departs City $X$ not earlier than time $0$. If City $Y$ is unreachable, report that fact.
The time it takes to transfer is ignorable. That is, at every city, you can transfer to a train that departs at the exact time your train arrives at that city.

Constraints

  • $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$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the earliest possible time you can reach City $Y$. If City $Y$ is unreachable, print -1 instead.

Sample Input 1

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

Sample Output 1

7

First, you take Railroad $1$ at time $0$ and go from City $1$ to City $2$. You arrive at City $2$ at time $2$.

Then, you take Railroad $2$ at time $4$ and go from City $2$ to City $3$. You arrive at City $3$ at time $7$.

There is no way to reach City $3$ earlier.

Sample Input 2

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

Sample Output 2

5

First, you take Railroad $2$ at time $0$ and go from City $3$ to City $2$. You arrive at City $2$ at time $3$.

Then, you take Railroad $1$ at time $3$ and go from City $2$ to City $1$. You arrive at City $1$ at time $5$.

Sample Input 3

3 0 3 1

Sample Output 3

-1

Sample Input 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

Sample Output 4

26

Input

题意翻译

AtCoder国家拥有编号为$1$至$N$的$N$个城市和编号为$1$至$M$的$M$条铁路。 铁路$i$连接着城市$A_i$和城市$B_i$之间，每到时间是$K_i$的倍数时，从双方城市分别开往另一城市的列车就会发车。这趟列车从出发到到达需要$T_i$的时间。 你现在在城市里。在乘坐时刻$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`。

Source/Category

加入题单

算法标签：