#481. [CSP-S 2026] 地铁

[CSP-S 2026] 地铁

地铁(subway)

CSP-S 2026 第二轮 · T2(赛题题意整理,测试数据为自制)

题目描述

一座城市有 mm 个地铁站和 nn 条地铁线路。第 vv 个站的地铁口到站厅步行需要 wvw_v 的时间;第 ii 条线路经过若干站,第 jj 个经过的站是 ai,ja_{i,j},从该站站厅到该线路站台步行需 ti,jt_{i,j} 的时间。各段通道反向步行耗时相同。

在同一条线路上坐车不计步行时间。要从一条线路换乘到另一条线路,必须先从前一条线路站台走到该站站厅,再进入后一条线路站台。中途换乘不需要走出地铁口,也不计中途站点的 wvw_v。每个地铁站最多有 dd 条线路经过,全部地铁站彼此可达。

给定 qq 次出行,从 xrx_r 站地铁口出发,抵达 yry_r 站地铁口。求每次出行的最小总步行时间。

输入格式

第一行五个整数 c,n,m,d,qc,n,m,d,q,其中 cc 是测试点编号,仅用于标识,不影响答案。

第二行 mm 个正整数 w1,…,wmw_1,\ldots,w_m。

随后 nn 行,第 ii 行先给出 kik_i,再依次给出 kik_i 对整数 (ai,j,ti,j)(a_{i,j},t_{i,j}),表示第 ii 条线路经过的站点及其站台通道耗时。同一线路不重复经过同一个站。

最后 qq 行,每行两个整数 xr,yrx_r,y_r(保证 xr≠yrx_r\ne y_r)。

输出格式

输出 qq 行,每行一个非负整数,表示对应出行的最小总步行时间。

输入输出样例 #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≤n≤5001\le n\le500,1≤m≤S=∑iki≤5×1051\le m\le S=\sum_i k_i\le5\times10^5,1≤d≤201\le d\le20,1≤q≤1051\le q\le10^5。

1≤wv,ti,j≤1091\le w_v,t_{i,j}\le10^9,1≤ki≤m1\le k_i\le m;所有地铁站彼此可达且每站经过的线路数不超过 dd。测试点编号 0≤c≤250\le c\le25。

注意: Hydro 使用标准输入输出;测试数据自行生成,并非 CCF 官方测试数据。