该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P9751 [CSP-J 2023] 旅游巴士

bus.zip

题目描述

给出一个 $n$ 个点 $m$ 条有向边的有向图。初始时间为 $0$ 。求：从点 $1$ 出发到点 $n$ 的最早时刻（没有方案则输出 $−1$）。

限制条件如下：
1、从点 $1$ 出发的时间 和 到达终点 $n$ 的时间 必须是 k 的倍数。
2、每条边的边权 $a_i$ 不是表示通过该边的时间，而是表示只有在当前时间 $\ge a_i$ 时才可以通过，通过任何一条边的时间为1。
3、任何时刻都不能在原地不动，即每一个时间点必须走一条边。

输入格式

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

输入的接下来 $m$ 行，每行包含 $3$ 个非负整数 $u _ i, v _ i, a_ i$，表示第 $i$ 条道路从地点 $u _ i$ 出发，到达地点 $v _ i$，道路的“开放时间”为 $a _ i$。

输出格式

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

输入输出样例 #1

输入 #1

5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1

输出 #1

6

说明/提示

【样例 #1 解释】

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

【样例 #2】

见附件中的 bus/bus2.in 与 bus/bus2.ans。

【数据范围】

对于所有测试数据有：$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$				无
$6 \sim 7$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	$a _ i = 0$
$8 \sim 10$				无
$11 \sim 13$			$100$	$a _ i = 0$
$14 \sim 15$				$u _ i \leq v _ i$
$16 \sim 20$				无