分数: 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