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