B 地铁（subway）

题目描述

B 市共有 $m$ 个地铁站，编号为 $1$ 到 $m$。每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。从第 $v$（$1\le v\le m$）个地铁站的地铁口走到站厅需要 $w_v$ 的时间。

B 市共有 $n$ 条地铁线路，编号为 $1$ 到 $n$，其中第 $i$（$1\le i\le n$）条线路经过 $k_i$ 个地铁站，编号依次为 $a_{i,1},a_{i,2},\ldots,a_{i,k_i}$。在第 $a_{i,j}$（$1\le j\le k_i$）个地铁站处，从站厅走到第 $i$ 条线路的站台需要 $t_{i,j}$ 的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站，即 $a_{i,1},a_{i,2},\ldots,a_{i,k_i}$ 两两不同。

由于空间有限，每个地铁站最多有 $d$ 条线路经过。此外，B 市的地铁网络是连通的，即任意两个地铁站都可以通过若干条线路互相到达。

小 R 有 $q$ 个出行计划。对于第 $r$（$1\le r\le q$）个出行计划，小 R 将从第 $x_r$ 个地铁站的地铁口出发，乘坐地铁到达第 $y_r$ 个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。小 R 希望每个出行计划的总步行时间都尽可能少。

你需要帮助小 R 求出，每个出行计划的最小总步行时间。

输入格式

输入的第一行包含五个非负整数 $c,n,m,d,q$，分别表示测试点编号、地铁线路数、地铁站数、每个地铁站最多被几条线路经过，以及出行计划数。特别地，若 $c=0$，则该测试点为样例。

输入的第二行包含 $m$ 个正整数 $w_1,w_2,\ldots,w_m$，依次表示从每个地铁站的地铁口走到站厅需要的时间。

输入的第 $i+2$（$1\le i\le n$）行包含 $1+2k_i$ 个正整数，其中第一个正整数为 $k_i$，表示第 $i$ 条线路经过的地铁站数；接下来 $2k_i$ 个正整数为 $a_{i,1},t_{i,1},a_{i,2},t_{i,2},\ldots,a_{i,k_i},t_{i,k_i}$，其中 $a_{i,j}$ 表示第 $i$ 条线路经过的第 $j$ 个地铁站，$t_{i,j}$ 表示从该地铁站的站厅走到第 $i$ 条线路的站台需要的时间。

输入的第 $r+n+2$（$1\le r\le q$）行包含两个正整数 $x_r,y_r$，分别表示第 $r$ 个出行计划的起点和终点所在的地铁站编号。

输出格式

输出 $q$ 行，其中第 $r$（$1\le r\le q$）行包含一个非负整数，表示第 $r$ 个出行计划的最小总步行时间。

样例

输入样例 1

0 2 5 20 2
4 1 9 2 5
3 1 5 2 7 4 6
3 2 3 3 4 5 7
1 3
1 2

输出样例 1

32
17

输入样例 2

0 3 7 20 2
8 3 6 1 7 2 9
3 1 4 2 5 5 100
3 2 6 3 1 7 2
4 3 2 5 100 4 6 6 7
1 6
2 3

输出样例 2

35
16

样例解释

样例 1：B 市有 5 个地铁站，从各地铁口走到站厅需要的时间分别为 $4,1,9,2,5$。第 1 条线路依次经过第 $1,2,4$ 个站，第 2 条线路依次经过第 $2,3,5$ 个站，两条线路在第 $2$ 个站相交。

对于第 1 个出行计划（$1\to 3$），总步行时间为 $w_1+t_{1,1}+(t_{1,2}+t_{2,2})+t_{2,3}+w_3=4+5+(7+3)+4+9=32$。

对于第 2 个出行计划（$1\to 2$），总步行时间为 $w_1+t_{1,1}+t_{1,2}+w_2=4+5+7+1=17$。

数据范围

对于所有测试数据，均有：

• $0\le c\le 25$，$1\le n\le 500$，$1\le m\le\sum_{i=1}^{n}k_i\le 5\times 10^5$，$1\le d\le 20$，$1\le q\le 10^5$；
• 对于所有 $v$，$1\le w_v\le 10^9$；
• 对于所有 $i$，$1\le k_i\le m$；
• 对于所有 $i,j$，$1\le a_{i,j}\le m$，$1\le t_{i,j}\le 10^9$；
• 对于所有 $i$，$a_{i,1},a_{i,2},\ldots,a_{i,k_i}$ 两两不同；
• 对于所有 $v$，经过第 $v$ 个地铁站的线路数均不超过 $d$；
• 任意两个地铁站都可以通过若干条线路互相到达；
• 对于所有 $r$，$1\le x_r,y_r\le m$，且 $x_r\ne y_r$。

测试点编号	$n\le$	$\sum k_i\le$	$d\le$	$q\le$	特殊性质
$1\sim 3$	$3$	$10$	$20$	$10$	无
$4\sim 6$	$50$	$300$		$200$
$7,8$	$200$	$400$			A
$9\sim 11$	$500$	$1000$		$10^5$
$12\sim 15$		$2\times 10^4$		$2000$	B
$16\sim 19$		$5\times 10^5$		$10^5$
$20,21$	$2$				无
$22,23$	$500$		$2$
$24,25$			$20$

特殊性质 A：每条线路至多经过 $2$ 个地铁站，即对于所有 $i$，均有 $k_i\le 2$。

特殊性质 B：对于所有线路经过的所有地铁站，从站厅走到对应线路站台的步行时间都相同，即存在正整数 $T$，使得对于所有 $i,j$，均有 $t_{i,j}=T$。

---

题目来源：CSP-S 2026 第二轮（CCF CSP-S 提高级）。 题面据洛谷 P17832 整理（文件输入输出改为标准输入输出）；本平台测试数据覆盖题面「测试点编号」表里的各档数据范围。