CF187B AlgoRace

有 $n$ 个城市，两两之间有直接连边，还有 $m$ 辆车。 已知每辆车经过边 $(i,j)$ 所需要的时间，即 $w_{i,j}$。你可以在到达一个城市之后选择换车，换车视为瞬间完成。对于每组询问 $(s,t,k)$，求从 $s$ 到 $t$ 的最短时间，其中换车总次数不超过 $k$，即全程使用的车次不超过 $k + 1$。注意：**同一辆车可以重复使用**。 询问共有 $r$ 组数据。

第一行为三个整数：$n, m, r$，分别代表城市总数、车辆总数、询问组数。 接下来是 $m$ 个 $n \times n$ 的矩阵，第 $i$ 个矩阵中第 $j$ 行、第 $k$ 列的数表示第 $i$ 辆车经过边 $(j,k)$ 需要的时间

对于每个询问，打印一个整数，表示在满足最多换 $k$ 次车的情况下，从 $s$ 到 $t$ 花费的最短时间

$n,m\le 60$ $w_{i,j}\le 10^6 $ $r\le 10^5$ $1\le s,t\le n,k\le 1000$ 感谢 @frankchenfu、@yuhaocheng 提供的翻译