← 返回题目列表

AtCoder · awc0068_d

D. 拥堵路口

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

分数: 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}。允许多次通过同一路口或同一条道路。

此路线所需的时间(以分钟为单位)是以下两个部分的总和:

  1. 公路旅行时间: 沿路线经过道路的次数,即 L 分钟。每条路的穿越时间正好 1 分钟,如果多次穿越同一条道路,则每次穿越都被统计。
  2. 路口通过时间: 对于每个 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