← 返回题目列表

AtCoder · awc0086_d

D. 最短路线

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

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