P16633 [GKS 2017 #F] Catch Them All

在 **Codejam**on **Go** 发布之后，你和你的许多朋友一样，走上城市街头，尽可能多地捕捉那些毛茸茸的小生物。游戏的目标是前往它们出现的位置，捕捉出现在你城市周围的 Codejamon。你想知道捕捉到所有 Codejamon 需要多长时间！ 你的城市包含 $N$ 个地点，编号为 $1$ 到 $N$。你从地点 $1$ 出发。有 $M$ 条双向道路（编号为 $1$ 到 $M$）。第 $i$ 条道路连接一对不同的地点 $(U_i, V_i)$，沿任一方向行驶都需要 $D_i$ 分钟。保证从地点 $1$ 出发，可以沿一条或多条道路到达任何其他地点。 在时间 $0$ 时，一只 Codejamon 会均匀随机地出现在除你当前位置以外的某个地点（时间 $0$ 时你的当前位置是地点 $1$）。均匀随机意味着它出现在除你当前位置以外的 $N-1$ 个地点中每一个的概率恰好为 $1/(N-1)$。当 Codejamon 出现的一瞬间，你可以立即开始朝它移动。当你到达包含 Codejamon 的地点时，你会立刻抓住它，然后新的 Codejamon 会立刻均匀随机地出现在除你当前位置以外的某个地点，依此类推。注意，任何时刻只有一只 Codejamon 存在，你必须先抓住当前这只，下一只才会出现。 给定你城市的地图，计算捕获 $P$ 只 Codejamon 的期望时间，假设你总是选择任意两个地点之间最快的路线。

输入的第一行包含一个整数 $T$：测试用例的数量。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含三个整数 $N$、$M$ 和 $P$，分别表示地点的数量、道路的数量和要捕捉的 Codejamon 数量。 然后，每个测试用例接着有 $M$ 行；第 $i$ 行包含三个整数 $U_i$、$V_i$ 和 $D_i$，表示第 $i$ 条道路连接地点 $U_i$ 和 $V_i$，沿任一方向行驶需要 $D_i$ 分钟。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是捕获 $P$ 只 Codejamon 的期望时间（以分钟为单位）。如果答案与正确答案的绝对误差或相对误差在 $10^{-4}$ 以内，则认为正确。

在样例 #1 中，我们只需要捕捉一只 Codejamon。它以相等的概率出现在地点 $2$、$3$、$4$ 和 $5$，这些地点离我们的起始地点 $1$ 的距离分别是 $1$、$3$、$2$ 和 $3$。因此，期望时间为 $(1 + 3 + 2 + 3) / 4 = 2.25$ 分钟。 在样例 #2 中，只有两个地点由一条道路连接。每次 Codejamon 出现时，它都会出现在除我们当前位置以外的另一个地点，我们必须沿道路到达那里。因此，我们走那条路 $200$ 次，每次 $5$ 分钟，总共 $1000$ 分钟。 样例 #3 使用与样例 #1 相同的地图。两只 Codejamon 出现的位置有 $16$ 种有序对可能性，计算得出期望为 $87/16 = 5.4375$ 分钟。 在样例 #4 中，我们需要捕捉的一只 Codejamon 将出现在地点 $2$ 或地点 $3$。如果它出现在地点 $2$，我们最好经由 $1$ 到 $3$ 再到 $2$ 的道路，花 $2$ 分钟到达，而不是走更耗时的 $1$ 到 $2$ 道路。因此，期望时间为 $(2 + 1) / 2 = 1.5$ 分钟。 ### 限制条件 $1 \le T \le 100$。 $N - 1 \le M \le (N \times (N - 1)) / 2$。 对于所有 $i$，$1 \le D_i \le 10$。 对于所有 $i$，$1 \le U_i < V_i \le N$。 对于所有 $i \ne j$，有 $U_i \ne U_j$ 和/或 $V_i \ne V_j$。（任意两个地点之间至多有一条道路。） 保证从地点 $1$ 出发，可以沿一条或多条道路到达任何其他地点。 **小数据集（测试集 1 – 可见）** $2 \le N \le 50$。 $1 \le P \le 200$。 **大数据集（测试集 2 – 隐藏）** $2 \le N \le 100$。 $1 \le P \le 10^9$。 翻译由 DeepSeek V4 Pro 完成