6516 - 地铁（subway 民间数据）[CSP-S 2026]
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 求出，每个出行计划的最小总步行时间。
从文件 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 条线路经过的地铁站数；接下来 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 个出行计划的起点和终点所在的地铁站编号。
输出到文件 subway.out 中。
输出 q 行，其中第 r（1 \le r \le q）行包含一个非负整数，表示第 r 个出行计划的最小总步行时间。
输入
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
输入
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 个地铁站的地铁口，总步行时间为
w_1+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 个地铁站的地铁口，总步行时间为
w_1+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 个地铁站的地铁口，总步行时间为
w_1+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 个地铁站的地铁口，总步行时间为
w_2+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 k_i），均有 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。
| 测试点编号 | 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 k_i），均有 t_{i,j}=T。
附件下载
subway.zip (9.39 MB)
