景区游览最短时间

题目描述

小 Y 计划在长假期间去一处心仪已久的景点游览。

景区地图共有 $n$ 处地点，地点之间连有 $m$ 条单向通行的道路。 $1$ 号地点为景区入口， $n$ 号地点为景区出口。将景区开门营业的时间记为 $0$ 时刻，从 $0$ 时刻起，每间隔 $k$ 单位时间便有一辆游览车到达景区入口，同时有一辆游览车从景区出口驶离。

游客步行通过每条道路的用时均为恰好 $1$ 单位时间。

小 Y 希望乘坐游览车到达景区入口，沿自选路径走到景区出口，再乘坐游览车离开——这意味着他到达和离开景区的时间都必须是 $k$ 的非负整数倍。由于客流较多，小 Y 在游览车离开景区前只想一直沿道路移动，不想在任何地点（包括入口和出口）或道路上停留。

出发前，小 Y 得知：景区对每条道路设置了「开放时间」 $a_i$ ，游客只有不早于 $a_i$ 时刻才能通过该道路。

请帮小 Y 设计游览方案，使他乘坐游览车离开景区的时间尽量地早。

输入的第一行包含 $3$ 个正整数 $n, m, k$ ，表示地点数、道路数以及游览车的发车间隔。

接下来 $m$ 行，每行包含 $3$ 个非负整数 $u_i, v_i, a_i$ ，表示第 $i$ 条道路从地点 $u_i$ 通向地点 $v_i$ ，道路的「开放时间」为 $a_i$ 。

输出一行，仅包含一个整数，表示小 Y 最早乘坐游览车离开景区的时刻。如果不存在符合要求的游览方案，输出 -1。

【样例 1 解释】

小 Y 可以在 $3$ 时刻到达景区入口，沿 $1 \to 3 \to 4 \to 5$ 的顺序走到景区出口，并在 $6$ 时刻离开。

【数据范围】

对于所有测试数据有： $2 \leq n \leq 10^4$ ， $1 \leq m \leq 2 \times 10^4$ ， $1 \leq k \leq 100$ ， $1 \leq u_i, v_i \leq n$ ， $0 \leq a_i \leq 10^6$ 。

测试点编号	$n \leq$	$m \leq$	$k \leq$	特殊性质
$1 \sim 2$	$10$	$15$	$100$	$a_i = 0$
$3 \sim 5$	$10$	$15$	$100$	无
$6 \sim 7$	$10^4$	$2 \times 10^4$	$1$	$a_i = 0$
$8 \sim 10$	$10^4$	$2 \times 10^4$	$1$	无
$11 \sim 13$	$10^4$	$2 \times 10^4$	$100$	$a_i = 0$
$14 \sim 15$	$10^4$	$2 \times 10^4$	$100$	$u_i \leq v_i$
$16 \sim 20$	$10^4$	$2 \times 10^4$	$100$	无

难度普及+/提高-

通过率 —

尝试 0

已通过 0

标签