97324 - 地铁subway（非官方数据）

时间限制 2 秒 内存限制 1024 MB

题目描述

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

B 市共有 $n$ 条地铁线路，编号为 $1$ 到 $n$ ，其中第 $i$ （ $1 \le i \le n$ ）条线路经过 $ki $个地铁站，编号依次为$ a{i,1},a{i,2},\ldots,a{i,ki} $。在第$ a{i,j} $（$ 1 \le j \le ki $）个地铁站处，从站厅走到第$ 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 求出，每个出行计划的最小总步行时间。

输入

从文件 subway.in 中读入数据。

输入的第一行包含五个非负整数 $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$ 条线路经过的地铁站数；接下来 $2ki $个正整数为$ a{i,1},t{i,1},a{i,2},t{i,2},\ldots,a{i,ki},t{i,ki} $，其中$ a{i,j} $表示第$ i $条线路经过的第$ j $个地铁站，$ t_{i,j} $表示从该地铁站的站厅走到第$ i$ 条线路的站台需要的时间。

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

输出

输出到文件 subway.out 中。

输出 $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

输出

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

输出

35
16

提示

样例 1 解释

B 市有 $5$ 个地铁站，从各地铁口走到站厅需要的时间分别为 $4,1,9,2,5$ 。

B 市有 $2$ 条地铁线路，其中第 $1$ 条线路依次经过第 $1,2,4$ 个地铁站，第 $2$ 条线路依次经过第 $2,3,5$ 个地铁站，两条线路在第 $2$ 个地铁站相交。

对于第 $1$ 个出行计划，小 R 将从第 $1$ 个地铁站前往第 $3$ 个地铁站：他可以先从第 $1$ 个地铁站的地铁口走到站厅，再走到第 $1$ 条线路的站台，乘坐第 $1$ 条线路到达第 $2$ 个地铁站后走回站厅，再走到第 $2$ 条线路的站台，乘坐第 $2$ 条线路到达第 $3$ 个地铁站后走回站厅，最后走到第 $3$ 个地铁站的地铁口，总步行时间为

$$ w1+t{1,1}+(t{1,2}+t{2,1})+t_{2,2}+w_3=4+5+(7+3)+4+9=32. $$

对于第 $2$ 个出行计划，小 R 将从第 $1$ 个地铁站前往第 $2$ 个地铁站：他可以先从第 $1$ 个地铁站的地铁口走到站厅，再走到第 $1$ 条线路的站台，乘坐第 $1$ 条线路到达第 $2$ 个地铁站后走回站厅，最后走到第 $2$ 个地铁站的地铁口，总步行时间为

$$ w1+t{1,1}+t_{1,2}+w_2=4+5+7+1=17. $$

样例 2 解释

B 市有 $7$ 个地铁站与 $3$ 条地铁线路，其中第 $1$ 条线路依次经过第 $1,2,5$ 个地铁站，第 $2$ 条线路依次经过第 $2,3,7$ 个地铁站，第 $3$ 条线路依次经过第 $3,5,4,6$ 个地铁站。

对于第 $1$ 个出行计划，小 R 将从第 $1$ 个地铁站前往第 $6$ 个地铁站：他可以先从第 $1$ 个地铁站的地铁口走到站厅，再走到第 $1$ 条线路的站台，乘坐第 $1$ 条线路到达第 $2$ 个地铁站后走回站厅，再走到第 $2$ 条线路的站台，乘坐第 $2$ 条线路到达第 $3$ 个地铁站后走回站厅，再走到第 $3$ 条线路的站台，乘坐第 $3$ 条线路到达第 $6$ 个地铁站后走回站厅，最后走到第 $6$ 个地铁站的地铁口，总步行时间为

$$ w1+t{1,1}+(t{1,2}+t{2,1})+(t{2,2}+t{3,1})+t_{3,4}+w_6=35. $$

对于第 $2$ 个出行计划，小 R 将从第 $2$ 个地铁站前往第 $3$ 个地铁站：他可以先从第 $2$ 个地铁站的地铁口走到站厅，再走到第 $2$ 条线路的站台，乘坐第 $2$ 条线路到达第 $3$ 个地铁站后走回站厅，最后走到第 $3$ 个地铁站的地铁口，总步行时间为

$$ w2+t{2,1}+t_{2,2}+w_3=16. $$

样例 3

见题目目录下的 subway/3.in 与 subway/3.ans。

该样例满足测试点 $4 \sim 6$ 的约束条件。

样例 4

见题目目录下的 subway/4.in 与 subway/4.ans。

该样例满足测试点 $9 \sim 11$ 的约束条件。

样例 5

见题目目录下的 subway/5.in 与 subway/5.ans。

该样例满足测试点 $12 \sim 15$ 的约束条件。

样例 6

见题目目录下的 subway/6.in 与 subway/6.ans。

该样例满足测试点 $16 \sim 19$ 的约束条件。

样例 7

见题目目录下的 subway/7.in 与 subway/7.ans。

该样例满足测试点 $22,23$ 的约束条件。

数据范围

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

$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 v \le m$ ），均有 $1 \le w_v \le 10^9$ ；
对于所有 $i$ （ $1 \le i \le n$ ），均有 $1 \le k_i \le m$ ；
对于所有 $i,j$ （ $1 \le i \le n$ ，$1 \le j \le ki $），均有$ 1 \le a{i,j} \le m $，$ 1 \le t_{i,j} \le 10^9$；
对于所有 $i$ （ $1 \le i \le n$ ），均有 $a{i,1},a{i,2},\ldots,a_{i,k_i}$ 两两不同；
对于所有 $v$ （ $1 \le v \le m$ ），经过第 $v$ 个地铁站的线路数均不超过 $d$ ；
任意两个地铁站都可以通过若干条线路互相到达；
对于所有 $r$ （ $1 \le r \le q$ ），均有 $1 \le x_r,y_r \le m$ ，且 $x_r \ne y_r$ 。

::cute-table{tuack} | 测试点编号 | $n \le$ | $\sum_{i=1}^{n} 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$ （ $1 \le i \le n$ ），均有 $k_i \le 2$ 。

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

来源

CSP-S 2026