← 返回题目列表

AtCoder · awc0029_d

D. 网络安装

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

分数: 366 分

问题陈述

Takahashi 在一家电信公司担任网络工程师,负责规划光纤电缆的安装。

有 N 城市中继站,编号从 1 to N。还有 M 地下隧道,每个隧道双向连接两个不同的中继站。的 i第隧道 (1 \leq i \leq M) 连接中继站 U_i 和中继站 V_i,宽度为 W_i 厘米。

高桥想要安装宽度为 1 的光缆束 K 距离中继站数据中心厘米 1 到中继站客户楼 N。为了使电缆束穿过隧道,该隧道的宽度必须至少为 K 厘米。因此,沿安装路线的所有隧道的宽度必须至少为 K 厘米。

这里,一个 路径 来自中继站 1 至中继站 N 是中继站序列 v_0, v_1, \ldots, v_L (L \geq 1) 满足以下所有条件:

  • v_0 = 1 和 v_L = N.
  • 对于每个 j (1 \leq j \leq L),存在连接中继站的隧道 v_{j-1} 和中继站 v_j.
  • v_0, v_1, \ldots, v_L 都是不同的(没有中继站被访问超过一次)。

这条路径经过 L 隧道。我们称之为 L 这 穿越的隧道数量 通过路径。

为了降低成本,高桥希望尽量减少穿越的隧道数量。

判断是否存在一条路径,该路径上所有隧道的宽度至少为 K 厘米。如果存在这样的路径,则输出所有这样的路径中经过的最小隧道数。如果不存在这样的路径,则输出 -1.

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • 最多有一条隧道连接任意一对中继站
  • 所有输入值均为整数

输入

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M

第一行包含中继站数量 N,隧道数量 M,以及电缆束的宽度 K (以厘米为单位),以空格分隔。

的 i- 以下各项 M 行 (1 \leq i \leq M) 包含两个中继站的号码 U_i, V_i 由 i第隧道,以及宽度 该隧道的 W_i (以厘米为单位),由空格分隔。

输出

如果存在来自中继站的路径 1 至中继站 N 沿路径的所有隧道的宽度至少为 K 厘米,输出单线上所有此类路径中穿过的隧道的最小数量。

如果不存在这样的路径,则输出 -1.


示例输入 1

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

示例输出 1

3

示例输入 2

4 4 10
1 2 15
1 3 5
2 3 8
3 4 12

示例输出 2

-1

示例输入 3

8 10 4
1 2 3
1 3 10
1 4 7
2 5 6
3 5 5
4 6 8
5 7 2
5 8 9
6 7 12
7 8 6

示例输出 3

3