题目描述

Chelsea 所在的州有 $N$ 座城市（编号从 $1$ 开始，其中城市 $1$ 是 Chelsea 所在的城市），并有 $M$ 条双向道路直接连接它们。（一对城市之间甚至可能由多条道路直接相连。）由于交通模式的变化，使用同一条道路所需的时间可能会因一天中的不同时刻而异，具体取决于旅程开始的时刻。（然而，在道路上行驶的方向并不重要——两个方向的交通状况总是同样糟糕！）所有道路上的行程都恰好从整点开始（也恰好于整点结束），并且在结束一条道路的行程后，可以立即开始另一条道路的行程。

Chelsea 热爱旅行，正在决定寒假去哪里度假。她想知道，根据她从自己城市出发的时间不同，她能多快到达其他各个目的地城市。（她前往目的地的路线中途可以经过其他城市。）你能回答她所有的问题吗？

输入格式

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

每个测试用例的第一行包含三个整数：城市数量 $N$，道路数量 $M$，以及 Chelsea 提出的问题数量 $K$。

接下来是 $2M$ 行——即 $M$ 对行。在每一对行中，第一行包含两个不同的整数 $x$ 和 $y$，描述连接第 $x$ 座城市和第 $y$ 座城市的一条双向道路。第二行包含 $24$ 个整数 $Cost[t]$ ($0 \le t \le 23$)，表示在 $t$ 点钟从该道路出发时，使用该道路所花费的时间（以小时计）。数据保证 $Cost[t]$ $\le$ $Cost[t+1]+1$ ($0 \le t \le 22$) 且 $Cost[23]$ $\le$ $Cost[0]+1$。

然后，接下来还有 $K$ 行。每行包含两个整数 $D$ 和 $S$，组成一个问题：如果 Chelsea 在 $S$ 点钟从城市 $1$ 出发，她最少需要多少小时才能到达城市 $D$？

输出格式

对于每个测试用例，输出一行形如 Case #x: 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），后面跟着 $K$ 个用空格分隔的整数，依次为对应问题的答案。如果对于某个问题，无论 Chelsea 选择哪些道路，她都无法到达目标城市，则对该问题输出 $-1$。

3
3 3 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 
2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1
3 3
3 1 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2
3 4
3 3 3
1 2
7 23 23 25 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
1 3
10 11 15 26 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
2 3
7 29 28 27 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
2 14
3 3
3 21

Case #1: 1 2
Case #2: 1 -1
Case #3: 17 26 13

提示

限制

$1 \le x, y \le N$。

$1 \le$ 所有 Cost 值 $\le 50$。

$1 \le D \le N$。

$0 \le S \le 23$。

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

$1 \le T \le 100$。

$2 \le N \le 20$。

$1 \le M \le 100$。

$1 \le K \le 100$。

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

$1 \le T \le 5$。

$2 \le N \le 500$。

$1 \le M \le 2000$。

$1 \le K \le 5000$。

翻译由 DeepSeek V4 Pro 完成