分数: 400 分
问题陈述
高桥生活在一个由 N 交叉路口和 M 双向道路。交叉点的编号从 1 to N,以及 i第条路连接路口 u_i 和交叉路口 v_i。不存在自环路(将交叉路口连接到自身的道路),并且最多有一条道路连接任意一对交叉路口。
对于每个交叉路口,连接到该交叉路口的道路数量称为 拥堵程度 那个十字路口的 。
高桥想要从十字路口出发 1 到交叉路口 N,但他不喜欢拥挤的十字路口。
高桥的路线表示为一系列交叉路口 p_0, p_1, p_2, \ldots, p_L (L \geq 1),其中 p_0 = 1, p_L = N,并且对于每个 j = 0, 1, \ldots, L-1,必须存在连接路口的道路 p_j 和交叉路口 p_{j+1}。允许多次通过同一路口或同一条道路。
此路线所需的时间(以分钟为单位)是以下两个部分的总和:
- 公路旅行时间: 沿路线经过道路的次数,即 L 分钟。每条路的穿越时间正好 1 分钟,如果多次穿越同一条道路,则每次穿越都被统计。
- 路口通过时间: 对于每个 p_1, p_2, \ldots, p_{L-1} (不包括第一个元素 p_0 和最后一个元素 p_L 的路线),如果该路口的拥堵程度为 K 或更多,额外 已产生 1 分钟。这是由于在红绿灯处等待或穿过人群造成的。如果同一个交集出现多次 p_1, p_2, \ldots, p_{L-1},对每次出现的情况进行检查,并为每次符合条件的出现添加附加时间。
仅作为第一个元素出现 p_0 和最后一个元素 p_L 的路线免于通过时间检查。例如,即使是交叉路口 1 or N,如果它们显示为以下任何一个 p_1, p_2, \ldots, p_{L-1},需经过时间检查。
求高桥从交叉路口行驶所需的最短时间 1 到交叉路口 N。如果没有从交叉路口出发的路线 1 到交叉路口 N 存在,输出 -1.
约束
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq u_i, v_i \leq N
- u_i \neq v_i
- 最多有一条道路连接任意一对交叉路口
- 所有输入值均为整数
输入
N M K u_1 v_1 u_2 v_2 \vdots u_M v_M
- 第一行包含交叉点的数量 N, 道路数量 M,以及拥塞级别阈值 K,用空格分隔。
- 的 i- 以下各项 M 行包含数字 u_i 和 v_i 由 i第条路,以空格分隔。
输出
在一行中输出高桥从路口行驶所需的最短时间(以分钟为单位) 1 到交叉路口 N。如果不存在这样的路由,则输出 -1.
示例输入 1
5 7 3 1 3 3 5 1 2 2 4 4 5 3 4 2 3
示例输出 1
3
示例输入 2
4 2 2 1 2 3 4
示例输出 2
-1
示例输入 3
8 12 4 1 2 1 3 2 3 2 4 3 5 4 5 4 6 5 6 5 7 6 8 7 8 3 4
示例输出 3
5