分数: 400 分
问题陈述
高桥在某城市担任送货员。该市有 N 位置,每个编号自 1 to N.
该市有 M 道路,每条道路双向连接两个地点。的 i第路 (1 \leq i \leq M) 连接位置 A_i 和位置 B_i,并且需要 C_i 沿着这条路行驶需要分钟。可能有多条道路连接同一对位置。
高桥从位置开始 1,配送中心所在位置,并将包裹配送至该地点 N 沿着道路行驶。从位置开始的路径 1 到位置 N 是位置序列 v_0 = 1, v_1, v_2, \ldots, v_k = N (k \geq 1) 这样对于每个 j (0 \leq j \leq k-1),至少存在一条道路连接位置 v_{j} 和位置 v_{j+1}。同一地点可能会被多次访问。
路径的行进时间确定如下。对于每个 j (0 \leq j \leq k-1),从连接位置的道路中选择一条道路 v_j 和位置 v_{j+1},所选道路的行驶时间之和就是该路径的行驶时间。
如果从位置开始的路径 1 到位置 N 存在,输出最小行程时间(分钟)。如果不存在路径则输出 -1.
约束
- 2 \leq N \leq 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq B_i \leq N
- A_i \neq B_i (无自环)
- 1 \leq C_i \leq 10^9
- 所有输入均为整数
输入
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
- 第一行包含位置数 N 和道路数量 M,用空格分隔。
- 的 i-th (1 \leq i \leq M) 以下内容 M 行包含两个位置的编号 A_i, B_i 由 i第条路和行车时间(以分钟为单位) 那条路的 C_i ,以空格分隔。
输出
输出从位置开始的路径的最短旅行时间 1 到位置 N 在一行上。如果不存在路径则输出 -1.
示例输入 1
4 4 1 2 3 2 4 5 1 3 2 3 4 7
示例输出 1
8
示例输入 2
3 1 1 2 10
示例输出 2
-1
示例输入 3
6 9 1 2 7 1 3 9 1 5 14 2 3 10 2 4 15 3 4 11 3 5 2 4 6 6 5 6 9
示例输出 3
20