RT，题目翻译出错，应为“换车总次数不超过k（最多乘坐k辆车，允许重复）”。

修改后的翻译：

---

题目描述

有$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)$需要的时间

接下来的$r$行描述了$r$个询问，每行包含三个数$s$，$t$，$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$

---

### 题目描述

有$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)$需要的时间

接下来的$r$行描述了$r$个询问，每行包含三个数$s$，$t$，$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$