← 返回题目列表

AtCoder · awc0039_d

D. 最快的送货路线

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

分数: 400 分

问题陈述

高桥是一名送货员。今天,他必须以最快的速度前往送货目的地,递送包裹。

送货区域包含 N 位置,编号自 1 to N。高桥从配送中心所在地出发 1 并旨在到达送货目的地所在位置 N.

有 M 地点之间的单向道路。的 i第路(1 \leq i \leq M) 是一条从位置出发的单向道路 U_i 到位置 V_i,并且需要 C_i 是时候沿着这条路旅行了。同一对位置可能有多条道路 (U_i, V_i).

高桥可能会多次经过同一位置。求从配送中心(位置 1)到交货目的地(位置 N).

保证位置 N 可从以下位置到达 1.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • 同一对 (U_i, V_i) 可能会多次给出
  • 位置 N 可从以下位置到达 1
  • 所有输入值均为整数

输入

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • 第一行包含位置数 N 和道路数量 M,用空格分隔。
  • 以下 M 每行描述一条路: i这些行中的第 (1 \leq i \leq M) 包含起点 U_i,终点 V_i,以及行程时间 C_i 的 i第条路,以空格分隔。这条路是从该地点出发的单向道路 U_i 到位置 V_i.

输出

打印从该地点出发所需的最短时间 1 到位置 N 作为单行上的整数。


示例输入 1

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

示例输出 1

6

示例输入 2

6 9
1 2 7
1 3 9
1 4 14
2 3 10
2 5 15
3 4 2
3 5 11
4 5 9
5 6 6

示例输出 2

26

示例输入 3

10 15
1 2 1000000000
1 3 500000000
2 4 300000000
3 4 200000000
3 5 400000000
4 6 100000000
5 6 150000000
5 7 250000000
6 7 50000000
6 8 200000000
7 8 100000000
7 9 300000000
8 9 150000000
8 10 400000000
9 10 100000000

示例输出 3

1200000000