P16506 [GKS 2015 #B] Travel

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$。

### 限制 $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 完成