← 返回题目列表

AtCoder · awc0033_d

D. 最便宜的通勤路线

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

分数: 400 分

问题陈述

高桥使用铁路网络进行通勤,其中包括 N 连接的站 M 行。车站编号从 1 to N。线 i 双向连接站 U_i 和车站 V_i,票价为 C_i 日元。

高桥每天需要从车站通勤 1, 离他家最近的车站, 到车站 N,距离他工作地点最近的车站。由于高桥的交通预算仅为 K 日元,他必须找到一条总票价最多为 K 日元。

这里,一个 路线 指的是从车站出发的路径 1 及后续线路依次到达车站 N。允许多次访问同一车站或多次使用同一条线路。一条路线的总票价是该路线所使用的所有线路的票价之和。如果多次使用同一条线路,则每次使用均需付费。

如果存在从车站出发的路线 1 到车站 N 总票价最多为 K 日元,输出所有此类航线中最低的总票价。如果不存在这样的路由,则输出 -1.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 可能有多条线路连接同一对车站
  • 1 \leq C_i \leq 10^9
  • 所有输入值均为整数

输入

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)第行,有关的信息 给出了 M 行。
  • 的 (1 + i)第 行包含两个车站 U_i, V_i 通过线路连接 i 和票价 C_i,以空格分隔。

输出

如果存在从车站出发的路线 1 到车站 N 总票价最多为 K 日元,输出一行中最低的总票价。如果不存在这样的路由,则输出 -1 一行。


示例输入 1

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

示例输出 1

8

示例输入 2

3 2 5
1 2 3
2 3 4

示例输出 2

-1

示例输入 3

6 8 15
1 2 4
1 3 2
2 4 5
3 4 3
2 5 7
4 5 1
4 6 8
5 6 2

示例输出 3

8