题目描述

Tom 正在城市里乘坐地铁，从一个车站前往另一个车站。

这座城市的地铁系统运作方式如下：

• 城市中有 $N$ 条地铁线路：线路 $1$、线路 $2$、……、线路 $N$。
• 对于每条地铁线路 $i$，设有 $SN_i$ 个车站。假设它们为 $S_{i,1}, S_{i,2}, \dots, S_{i,SN_i}$。这些车站从一端终点站排列至另一端终点站。地铁双向运行。换句话说，地铁从 $S_{i,1}$ $\to$ $S_{i,2}$ $\to$ ... $\to$ $S_{i,SN_i}$ 方向运行，也从 $S_{i,SN_i}$ $\to$ $S_{i,SN_i-1}$ $\to$ ... $\to$ $S_{i,1}$ 方向运行。你可以在任意车站上车，并在任意车站下车。从一个车站到相邻的下一个车站需要花费一定的时间。从 $S_{i,1}$ 到 $S_{i,2}$ 需要 $Time_{i,1}$ 分钟，从 $S_{i,2}$ 到 $S_{i,3}$ 需要 $Time_{i,2}$ 分钟，以此类推。反向运行花费的时间相同。
• 有 $M$ 条换乘通道。每条换乘通道连接两条不同地铁线路上的车站。无论朝哪个方向，通过一条通道都需要花费一定的时间。你可以在通道的一端下地铁，然后步行穿过通道到达另一端的车站。
• 当你到达线路 $i$ 的某个地铁站时，你需要等待 $W_i$ 分钟才能搭乘下一班地铁。

现在，你打算从一个车站前往另一个车站。请计算你所需的最短时间。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例以一个整数 $N$ 开始，表示地铁线路的数量。接下来是 $N$ 条地铁线路的描述。每条地铁线路的描述以两个整数 $SN_i$ 和 $W_i$ 开始，分别表示车站数量和预期的等待时间（以分钟计）。接下来一行包含 $SN_i-1$ 个整数，依次为 $Time_{i,1}$, $Time_{i,2}$, ..., $Time_{i,SN_i-1}$，描述车站间的运行时间。

在所有地铁线路的描述之后，是一个整数 $M$，表示换乘通道的数量。接下来的 $M$ 行描述每条通道。每条通道的描述包含 5 个整数 $m1_i$, $s1_i$, $m2_i$, $s2_i$, $t_i$，表示该通道连接车站 $S_{m1_i,s1_i}$ 和车站 $S_{m2_i,s2_i}$。通过该通道的步行时间为 $t_i$。

再接下来一行包含一个整数 $Q$，表示查询的数量。接下来的 $Q$ 行每行包含 4 个整数 $x1$, $y1$, $x2$, $y2$，表示你将从车站 $S_{x1,y1}$ 前往车站 $S_{x2,y2}$。

输出格式

对于每个测试用例，首先输出一行 "Case #x:"，其中 $x$ 是测试用例编号（从 $1$ 开始），随后输出 $Q$ 行，每行先输出一个空格，再输出一个整数 $y$，即该次查询所需的最短时间。如果无法到达，则对该查询输出 $-1$。

2

2
5 3
3 5 7 3
4 2
1 1 1
1
1 2 2 2 1
1
1 1 2 4

2
5 3
3 5 7 3
4 2
1 1 1
2
1 2 2 2 1
2 4 1 4 1
1
1 1 1 5

Case #1:
 11
Case #2:
 18

提示

限制

$1 \le T \le 100$.

$1 \le W_i \le 100$.

$1 \le Time_{i,j} \le 100$.

$1 \le m1_i \le N$.

$1 \le s1_i \le SN_{m1_i}$.

$1 \le m2_i \le N$.

$1 \le s2_i \le SN_{m2_i}$.

$m1_i$ 与 $m2_i$ 不相同。

$1 \le t_i \le 100$.

$1 \le Q \le 10$.

$1 \le x1 \le N$.

$1 \le y1 \le SN_{x1}$.

$1 \le x2 \le N$.

$1 \le y2 \le SN_{y2}$.

车站 $S_{x1,y1}$ 与车站 $S_{x2,y2}$ 不相同。

小数据集（测试集 1 - 可见）

$1 \le N \le 10$.

$0 \le M \le 10$.

$2 \le SN_i \le 100$.

每个测试用例中的车站总数不超过 $100$。

大数据集（测试集 2 - 隐藏）

$1 \le N \le 100$.

$0 \le M \le 100$.

$2 \le SN_i \le 1000$.

每个测试用例中的车站总数不超过 $1000$。

翻译由 DeepSeek V4 Pro 完成