← 返回题目列表

AtCoder · awc0071_d

D. 交货

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

分数: 400 分

问题陈述

高桥正尝试穿过城镇进行送货。

该镇有 N 位置编号自 1 to N,和 M 连接两对地点的道路。的 i第条路双向连接位置 U_i 和位置 V_i,并且需要 C_i 遍历时间。

高桥目前位于该位置 S。他要投递的包裹已放置在指定地点 G,目的地是位置 T.

高桥必须首先前往地点 G 领取包裹,然后递送至指定地点 T。在旅行期间,他可能多次经过同一个地点或同一条道路。

求高桥从该位置出发所需的最短时间 S,通过位置 G,并到达位置 T。如果无法到达地点 G 来自位置 S,或无法到达位置 T 来自位置 G,输出 -1.

约束

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 1.5 \times 10^5
  • 1 \leq S, G, T \leq N
  • S, G, T 都是不同的
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • 至多有一条道路连接任意一对位置(不存在明显的 i, j 这样 (U_i, V_i) 和 (U_j, V_j) 是同一对,无论顺序如何)
  • 所有输入值均为整数

输入

N M S G T
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • 第一行包含 N 代表位置数量, M 代表道路数量, S 代表高桥的初始位置, G 代表包裹的位置,以及 T 代表目的地,以空格分隔。
  • 以下 M 线提供有关道路的信息。
  • 的 (1 + i)第行表示 i第条路连接位置 U_i 和位置 V_i,并且需要 C_i 遍历时间。

输出

单行输出高桥从位置出发所需的最短时间 S,到指定地点领取包裹 G,然后移动到位置 T。如果这样的行程不可能,则输出 -1.


示例输入 1

4 4 1 2 4
1 2 3
2 4 5
1 3 10
3 4 1

示例输出 1

8

示例输入 2

5 2 1 3 5
1 2 4
3 4 7

示例输出 2

-1

示例输入 3

8 10 1 5 8
1 2 4
2 3 2
3 5 3
1 4 10
4 5 1
5 6 2
6 8 3
5 7 8
7 8 1
3 6 5

示例输出 3

14

示例输入 4

12 18 2 9 12
1 2 5
1 3 2
2 4 4
3 4 1
3 5 7
4 6 3
5 6 2
6 7 4
7 8 6
8 9 1
6 9 10
4 10 8
10 11 2
11 12 3
9 12 5
5 10 1
2 5 9
7 11 2

示例输出 4

22

示例输入 5

3 2 1 2 3
1 2 1000000000
2 3 1000000000

示例输出 5

2000000000