SP698 PLHOP - Plane Hopping

这个人异常富有，以至于每次在任何两个地点之间旅行时，总是至少乘坐 $K$ 次航班。在一个拥有 $N$ 座城市的地区内，我们需要确定他在所有城市对之间旅行的最低费用。对于这样的富人，还有特别的航班可以让他从某个城市飞回该城市。

首先输入 $T$，表示测试用例的数量。 对于每个测试用例，依次输入： - 两个整数 $K$ 和 $N$。 - 一个 $N \times N$ 的矩阵，表示机票的费用。矩阵中的第 $i$ 行第 $j$ 列的数字表示从城市 $i$ 飞往城市 $j$ 的机票费用。所有数字用空格分隔。 **数据范围：** - $T \leq 20$ - $N \leq 50$ - $K \leq 10^9$ - 每张机票的费用 $\leq 100$ - 输出矩阵中的每个元素都是一个可以放入 64 位整数的数字。

对于第 $i$ 个测试用例，首先输出「Region #i:」。 接着输出一个 $N \times N$ 的矩阵，其中第 $i$ 行第 $j$ 列的数值表示从城市 $i$ 到城市 $j$ 至少乘坐 $K$ 次航班的最低费用。每行的数值用空格分隔。每个测试用例输出完成后需要留一个空行，即使是最后一个测试用例也不例外。 **本翻译由 AI 自动生成**