AdditionalFile4835.zip

P9402 [POI 2020/2021 R3] Droga do domu

题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Droga do domu。

d1t1。

题目描述

$n$ 个点，$m$ 条边，无重边自环，边有长度。

$1$ 号点是学校，$n$ 号点是家。

$s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。

在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。

只计算路上时间和等车时间。换乘时间不计。

输入格式

第一行：五个整数 $n,m,s,k,t$。

接下来 $m$ 行：每行三个整数 $a,b,c$，表示有一条边连接 $a,b$，长度为 $c$。

接下来 $2s$ 行：每两行描述一条公交线路：

• 第一行三个整数 $l,x,y$，表示它共停靠 $l$ 个点，第一班在时刻 $x$ 发车，每两班之间时间间隔为 $y$。
• 第二行 $l$ 个整数 $v_1,\dots,v_l$，依次为它停靠的 $l$ 个点。

输出格式

一行一个整数，答案。

如果不能到家，那么输出一行一个字符串 NIE。

输入输出样例 #1

输入 #1

4 4 2 1 1
1 2 2
2 3 4
1 3 3
4 3 2
4 0 10
1 2 3 4
3 2 7
1 3 2

输出 #1

8

输入输出样例 #2

输入 #2

10 45 17 10 123
1 2 1
1 3 100
1 4 100
1 5 100
1 6 100
1 7 100
1 8 100
1 9 100
1 10 100
2 3 1
2 4 100
2 5 100
2 6 100
2 7 100
2 8 100
2 9 100
2 10 100
3 4 1
3 5 100
3 6 100
3 7 100
3 8 100
3 9 100
3 10 100
4 5 1
4 6 100
4 7 100
4 8 100
4 9 100
4 10 100
5 6 1
5 7 100
5 8 100
5 9 100
5 10 100
6 7 1
6 8 100
6 9 100
6 10 100
7 8 1
7 9 100
7 10 100
8 9 1
8 10 100
9 10 1
2 0 1
1 2
2 0 1
1 3
2 0 1
2 3
2 0 1
2 4
2 0 1
3 4
2 0 1
3 5
2 0 1
4 5
2 0 1
4 6
2 0 1
5 6
2 0 1
5 7
2 0 1
6 7
2 0 1
6 8
2 0 1
7 8
2 0 1
7 9
2 0 1
8 9
2 0 1
8 10
2 0 1
9 10

输出 #2

132

输入输出样例 #3

输入 #3

见附件

输出 #3

1000000102

输入输出样例 #4

输入 #4

见附件

输出 #4

11100000071

说明/提示

样例解释：

对于全部数据，$2\leq n\leq 10000$，$1\leq m\leq 50000$，$1\leq s\leq 25000$，$0\leq k\leq 100$，$0\leq t\leq 10^9$，$1\leq c\leq 10^9$，$2\leq l\leq n$，$0\leq x\leq 10^9$，$1\leq y\leq 10^9$，$1\leq a,b,v\leq n$，$\sum l\leq 50000$。

子任务编号	限制	分数
1	$k=n$	20
2	$v_i<v_{i+1}$
3	$l=2$
4	$t=0,x=0,y=1$
5

#4835. 「POI 2020/2021 R3」Droga do domu

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Droga do domu

Bajtogród 的路网由 $n$ 个路口和 $m$ 条双向道路组成。每条道路连接两个不同的路口，且任意两个路口之间最多只有一条直接道路。道路可能经过隧道或高架桥。

路口 $1$ 附近有一所学校，Bajtek 每天在那里上学，而路口 $n$ 附近是他的家。早上，父母会开车送他去学校，但放学后他需要自己乘坐公共交通回家。今年公交车的时刻表又一次调整了。由于 Bajtogród 只提供单程票，每次上车都需要检票，Bajtek 决定制定一个最快的回家计划，且换乘次数不超过 $k$ 次。请你帮帮他！

每条公交线路的车辆都会按照固定的路线行驶，经过某些路口，并在每个路口停靠，供乘客上下车。同一线路的公交车会按照固定的时间间隔发车（具体细节见输入格式）。我们假设以下时间可以忽略不计：

• 公交车在路口的停靠时间；
• 从一辆公交车换乘到另一辆公交车的时间（假设无需等待）；
• 从学校走到路口 $1$ 以及从路口 $n$ 走回家的时间。

输入格式

输入的第一行包含五个整数 $n, m, s, k, t$ $(2 \leq n \leq 10000, 1 \leq m \leq 50000, 1 \leq s \leq 25000, 0 \leq k \leq 100, 0 \leq t \leq 10^{9})$，分别表示路口数量、道路数量、公交线路数量、Bajtek 最多允许的换乘次数，以及他离开学校的分钟数。路口编号从 $1$ 到 $n$。

接下来的 $m$ 行描述道路，每行包含三个整数 $a, b, c$ $(1 \leq a, b \leq n, a \neq b, 1 \leq c \leq 10^{9})$，表示编号为 $a$ 和 $b$ 的路口之间有一条双向道路，乘坐任何经过这条路的公交车通过它需要 $c$ 分钟。每对无序路口对 $\{a, b\}$ 在输入中最多出现一次。

接下来的 $2s$ 行描述公交线路，每条线路的描述占用两行。第一行包含三个整数 $\ell, x, y$ $(2 \leq \ell \leq n, 0 \leq x \leq 10^{9}, 1 \leq y \leq 10^{9})$，第二行包含 $\ell$ 个两两不同的整数 $v_{1}, v_{2}, \ldots, v_{\ell}$ $(1 \leq v_{i} \leq n)$。这表示该线路的公交车从路口 $v_{1}$ 在 $x + j \cdot y$ $(j = 0, 1, 2, \ldots)$ 分钟发车，然后依次经过路口 $v_{2}, v_{3}, \ldots, v_{\ell}$。保证对于 $1 \leq i < l$，路口 $v_i$ 和 $v_{i+1}$ 之间存在一条道路。

所有公交线路的 $\ell$ 之和不超过 $50000$。

输出格式

你的程序应输出一行，包含一个整数，表示 Bajtek 从学校离开后能到达家的最早分钟数。如果 Bajtek 无法在 $t$ 分钟后回家，则应输出 NIE。

样例 1

输入

4 4 2 1 1
1 2 2
2 3 4
1 3 3
4 3 2
4 0 10
1 2 3 4
3 2 7
1 3 2

输出

8

下图展示了样例中的 Bajtogród 路网。圆圈表示路口，圆圈内的数字是路口编号；线条表示道路，线条旁的数字是经过该道路的行车时间。第 $1$ 条公交线路的路线用红色标记，第 $2$ 条公交线路的路线用蓝色标记。

Bajtek 在 $t=1$ 分钟离开学校，在路口 $1$ 等待第 $2$ 条线路的公交车（第 $2$ 分钟到达），乘坐它到路口 $3$（第 $6$ 分钟到达），然后在路口 $3$ 换乘第 $1$ 条线路的公交车（第 $6$ 分钟到达路口 3），最终在第 $8$ 分钟到达家。

如果 $k=0$，Bajtek 必须在路口 $1$ 等待第 $1$ 条线路的公交车（第 $10$ 分钟发车），并在第 $18$ 分钟到达家。

样例 2

见附加文件下 [dro1.in](file:dro1.in) 和 [dro1.out](file:dro1.out)。

该样例满足 $n=10, m=45, k=10, t=123$，编号相邻的路口之间有长度为 $1$ 的道路，其他路口对之间有长度为 $100$ 的道路；公交车从 $0$ 分钟开始运行，每分钟都有车在相邻或相隔 $1$ 的路口之间运行，答案是 $132$；

样例 3

见附加文件下 [dro2.in](file:dro2.in) 和 [dro2.out](file:dro2.out)。

该样例满足 $n=103, m=102, k=100, t=0$，编号相邻的路口之间有长度为 $1$ 的道路，其他路口对之间没有直接道路；有一辆公交车在 $10^{9}$ 分钟发车，经过路口 $(1, 2, 3, \ldots, n)$，还有一些公交车从 $0$ 分钟开始运行，覆盖所有相邻路口对，答案是 $10^{9}+102$；

样例 4

见附加文件下 [dro3.in](file:dro3.in) 和 [dro3.out](file:dro3.out)。

该样例满足 $n=10000, m=17891, s=7891, k=50, t=0$，答案是 $11100000071$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$k=n$	$20$
$2$	每条公交线路：$v_{i} < v_{i+1}$	$20$
$3$	每条公交线路：$\ell=2$	$20$
$4$	$t=0$ 且每条公交线路：$x=0, y=1$	$20$
$5$	无附加限制	$20$