4516. 地铁

【题目描述】

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

B 市共有n 条地铁线路，编号为1 到n，其中第i (1 ≤ i ≤ n) 条线路经过ki  个地铁站，编号依次为ai,1,ai,2,...,ai,ki。在第ai,j  (1 ≤j ≤ ki) 个地铁站处，从站厅走到第i条线路的站台需要ti,j  的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站，即ai,1,ai,2 ,...,ai,ki  两两不同。

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

小R 有q 个出行计划。对于第r (1 ≤ r ≤ q) 个出行计划，小R 将从第xr  个地铁站的地铁口出发，乘坐地铁到达第yr  个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。小R 希望每个出行计划的总步行时间都尽可能少。你需要帮助小R 求出，每个出行计划的最小总步行时间。

【输入格式】

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

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

输入的第二行包含m 个正整数w1 ,w2 ,...,wm，依次表示从每个地铁站的地铁口走到站厅需要的时间。

输入的第i + 2 (1 ≤ i ≤ n) 行包含1 + 2ki  个正整数，其中第一个正整数为ki，表示第i 条线路经过的地铁站数；接下来2ki  个正整数为ai,1,ti,1,ai,2,ti,2,...,ai,ki,ti,ki，其中ai,j  表示第i 条线路经过的第j 个地铁站，ti,j  表示从该地铁站的站厅走到第i 条线路的站台需要的时间。输入的第r + n + 2 (1 ≤ r ≤ q) 行包含两个正整数xr ,yr，分别表示第r 个出行计划的起点和终点所在的地铁站编号。

【输出格式】

输出到文件subway.out 中。

输出q 行，其中第r (1 ≤ r ≤ 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

【样例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 +t1 ,1 + (t1 ,2 +t2 ,2 ) +t2 ,3 +w3  = 4 + 5 + (7 + 3) +4 + 9 = 32 .

对于第2 个出行计划，小R 将从第1 个地铁站前往第2 个地铁站：他可以先从第1 个地铁站的地铁口走到站厅，再走到第1 条线路的站台，乘坐第1 条线路到达第2 个地铁站后走回站厅，最后走到第2 个地铁站的地铁口，总步行时间为w 1 +t1 ,1 +t1 ,2 +w2  = 4 + 5 + 7 + 1 = 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

【样例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 +t1 ,1 + (t1 ,2 +t2 ,2 ) + (t2 ,3 +t3 ,3 ) +t3 ,6 +w6  = 35 .

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

【数据规模与约定】

【来源】

在此键入。