SP9938 DISNEY - Disney Fastpass

在一座公园内，游客的旅程须从编号为 1 的唯一入口出发，并最终回到此地。公园中有若干个景点和道路。 给出 $T$ 个测试用例，每个测试用例如下描述： 首先给出三个整数 $N$、$M$ 和 $K$： - $N$ 表示地点的数量（1 号地点是入口）， - $M$ 表示现有道路的数量， - $K$ 表示感兴趣的景点的数量。 接下来有 $M$ 行，每行三个整数 $A$、$B$ 和 $D$，表示在地点 $A$ 和地点 $B$ 之间的旅行耗时为 $D$ 分钟。 然后是 $K$ 行，每行描述一个感兴趣的景点，包括整数 $P_i$、$T_i$、$FT_i$、$N_i$，以及一组地点编号 $F_{i,1}$ 到 $F_{i,N_i}$。其中： - $P_i$ 表示景点所在位置， - $T_i$ 是没有快速通行证时的等待时间， - $FT_i$ 是持有快速通行证时的等待时间， - $N_i$ 表示可以领取该景点快速通行证的地点数量，这些地方的编号为 $F_{i,1}$ 到 $F_{i,N_i}$。 假设所有地点都是直接或间接相连的，并且任何两个地点之间至多有一条道路。同一个地点可能会有多个景点。

The first line contains an integer **T** (1 ≤ **T** ≤ 25), indicating the number of test cases. Each test case contains several lines. The first line contains three integers **N**, **M**, **K** (1 ≤ **N** ≤ 50, 0 ≤ **M** ≤ **N**(**N**-1)/2, 0 ≤ **K** ≤ 8), indicating the number of locations(starting with 1, and 1 is the only gate of the park where the trip must be started and ended), the number of roads and the number of interested attractions. The following **M** lines each contains three integers **A**, **B**, **D** (1 ≤ **A**, **B** ≤ **N**, 0 ≤ **D** ≤ 10 $ ^{4} $ ) which means it takes **D** minutes to travel between location **A** and location **B**. The following **K** lines each contains several integers **P** $ _{i} $ , **T** $ _{i} $ , **FT** $ _{i} $ , **N** $ _{i} $ , **F** $ _{i,1} $ , **F** $ _{i,2} $ ... **F** $ _{i,Ni} $ -1, **F** $ _{i,Ni} $ , (1 ≤ **P** $ _{i} $ , **N** $ _{i} $ , **F** $ _{i,j} $ ≤ **N**, 0 ≤ **FT** $ _{i} $ ≤ **T** $ _{i} $ ≤ 10 $ ^{4} $ ), which means the i-th interested attraction is placed at location **P** $ _{i} $ and there are **N** $ _{i} $ locations **F** $ _{i,1} $ , **F** $ _{i,2} $ ... **F** $ _{i,Ni} $ where you can get the FastPass for the _i_-th attraction. If you come to the _i_-th attraction with its FastPass, you need to wait for only **FT** $ _{i} $ minutes, otherwise you need to wait for **T** $ _{i} $ minutes. You can assume that all the locations are connected and there is at most one road between any two locations. Note that there might be several attractions at one location.

对于每个测试用例，输出一行，格式为：“Case #X: Y”，其中 $X$ 为测试用例编号（从 1 开始），$Y$ 是完成整个旅程所需的最短时间。 **本翻译由 AI 自动生成**