分数: 400 分
问题陈述
高桥是一家快递公司的送货司机。今天的工作,他需要从配送中心出发,沿途经过特定的中转点,将包裹投递到最终目的地。
高桥的指定区域包含 N 位置,每个编号自 1 to N。地点 1 是配送中心,位置 N 是最终目的地。有 M 连接地点的道路,每条道路都是双向的,并且在任一方向上行驶所需的时间相同。的 i第路(1 \leq i \leq M) 连接位置 U_i 和位置 V_i,并且需要 沿着这条路行驶 C_i 分钟。
对于今天的交货,高桥需要在该地点领取另一个包裹 K,作为中继点,所以他必须经过位置 K。具体来说,高桥从所在地出发 1 到位置 K,然后从位置 K 到位置 N。在旅行期间,他可能多次访问同一地点并多次使用同一条道路。请注意,如果 K = 1,配送中心同时作为中继点,如果 K = N,最终目的地也是中转点。
求高桥从配送中心(位置 1)通过中继点(位置 K)到最终目的地(位置 N)。如果至少有一条路径 - 从位置 1 到位置 K 或从位置 K 到位置 N — 不存在,输出 -1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i (无自环)
- 1 \leq C_i \leq 10^9
- 可能有多条道路连接同一对位置
- 所有输入值均为整数
- 当存在解时,保证答案最多为 2 \times 10^{14}
输入
N M K U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
- 第一行包含位置数 N, 道路数量 M,以及中继点编号 K,用空格分隔。
- 从第 2 行到 (M + 1)第行,给出了每条道路的信息。
- 的 (1 + i)- 第行包含位置编号 U_i 和 V_i 由 i第 条路,以及行车时间 C_i (以分钟为单位)该路,以空格分隔。
输出
在单行上输出高桥从某个地点出发的最短总行程时间(以分钟为单位) 1 通过位置 K 到位置 N。如果无法到达,则输出 -1.
示例输入 1
5 6 3 1 2 2 2 3 3 1 3 10 3 4 4 4 5 2 3 5 7
示例输出 1
11
示例输入 2
4 2 3 1 2 5 3 4 3
示例输出 2
-1
示例输入 3
8 10 5 1 2 3 1 3 2 2 4 5 2 5 4 3 5 6 4 5 3 5 6 4 5 7 2 6 8 5 7 8 3
示例输出 3
12