← 返回题目列表

AtCoder · code_festival_relay_i

I. 等待红绿灯

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

問題文

陆路运输公司陆道社的员工淀粉酶伯爵前往某城镇运送包裹。这座城市是 连接n 路口和路口 m 它是由真实的道路组成,在交叉路口有 它们的编号最大为 1 到 n 。


每个十字路口都有一个红绿灯。 1 每个交通灯都是蓝色或红色。 2 它有两种状态。时间 t = 0, 1, 2, ... 处的交叉路口 i 中交通灯的状态由参数确定 a_i, b_i, c_i 确定如下。

  • 第一 c_i 秒,即 t = 0, 1, ..., c_{i}-1 为红色
  • 然后, a_i 第二个蓝色和 b_i 秒红色重复

颜色从蓝色变为红色的时间(例如 t = c_i + a_i ),交通灯为红色,由红变绿的时间(例如: 请注意, t = c_i 时交通灯为绿色。


无论交通灯状态如何,您都可以到达每个路口,但只有在交通灯为绿色时才能从该路口出发。此外,除去红绿灯的等待时间,十字路口 您可以在 0 秒内完成它。


现在,是时候计算淀粉酶了。 0 处的交叉点 当您到达 s 时,前往十字路口 求前往 d 所需的最短时间。


入力

输入按以下格式给出。

n m s d
a_1 b_1 c_1
...
a_n b_n c_n
x_1 y_1 t_1
...
x_m y_m t_m
  • 1 行包含一个表示交叉点数量的整数。 n (2 \leq n \leq 100{,}000), 表示道路数量的整数 m (1 \leq m \leq min(n(n-1)/2, 10^5)), 代表起点交集的整数 s (1 \leq s \leq n)和一个表示目标点交点的整数 d (1 \leq d \leq n)。 来自行
  • s \neq d 有保证。
  • 继续 n 行提供有关每个十字路口交通灯的信息。
  • a_i, b_i, c_i (1 \leq a_i, b_i, c_i \leq 1{,}000{,}000{,}000) 是 第i 个十字路口的红绿灯是 c_i 秒为红色,然后 a_i 第二个蓝色和 b_i 表示重复第二个红色。
  • 继续 m 行提供有关每条道路的信息。
  • x_i, y_i (1 \leq x_i, y_i\leq n)和 t_i (0 \leq t_i \leq 1{,}000{,}000{,}000) 是 第i 路口 在 x_i 和 y_i 之间移动 这意味着需要 t_i 秒。
  • 给定的图是连通的,并且保证不包含自边或重边。

出力

交差点 s 到交叉路口 移动到 d 所需的最短时间 1 按行输出。

在末尾使用换行符,并且不要包含不必要的字符或空行。


入力例1

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

出力例1

8

作为起点的交叉路口 1 红绿灯时间到了 它首先在 4 中变成蓝色,然后从那里开始 4 需要几秒钟 只需移至 2 。


入力例2

4 4 4 2
2 4 8
9 9 9
2 8 4
3 3 3
1 2 8
1 4 6
2 3 6
3 4 3

出力例2

17