赛车车技

题目描述

一场声势浩大的赛车比赛即将开始。赛车比赛地图上有 n 个站点，任意两个站点间都有双向道路相连，且道路只可能在站点处相交。在赛车比赛地图上确定了比赛的起点和终点后，赛车手可以在比赛地图上规划自己的行车路线，以最短时间完成从起点到终点的赛程。每个选手可以选择 m 款不同型号的赛车参赛。在每个站点处均可提供足够多任一型号赛车用于比赛。比赛中，选手可以在任何站点更换赛车，更换赛车花费的时间忽略不计，但赛程中每个选手更换赛车的总次数受到限制。

赛车手 F 驾驶型号为 a ( 1≤a≤m )的赛车从站点 i ( 1≤ i ≤n )经连接站点 j ( 1≤ j≤ n )的赛道 (i ,j ) 到达站点 j 所需时间为E (a ,i ,j ) 。由于地形和路况的原因，通常情况下E(a ,i ,j )≠ E( a,j ,i )。

由于赛前并不知道比赛的起点和终点，赛车手 F 希望根据自己的驾驶技术，预测不同情况下，完成赛程所需的最短时间。也就是说，如果给出 3 个正整数 1≤i ,j ,k ≤n ，其中， i 为起点， j 为终点， k 为最多更换赛车的次数，据此计算出赛车手 F 完成赛程所需的最短时间。

输入格式

第 1 行有 3 个整数 n， m， q ，分别表示比赛地图的站点数，不同型号的赛车数，以及预测次数。接下来给出 m 个 n× n 矩阵。其中，第 a 个 n ×n 矩阵中，第 i 行，第 j 列的值为 E(a ,i ,j ) 。且满足 E(a ,i ,j )≥ 0 。当 i= j时，给出 E(a ,i ,i )= 0 。

接下来的 q 行中是 q 次预测。每次预测给出 3 个正整数 1≤ i,j ,k≤ n ，其中， i 为起点，j 为终点， k 为最多更换赛车的次数。

输出格式

将计算出的 q 次预测结果依次输出。

样例 #1

样例输入 #1

5 3 3
0 9 2 9 9
1 0 9 9 9
9 9 0 9 2
9 9 9 0 9
9 9 9 2 0
0 9 9 9 9
9 0 9 9 9
9 9 0 9 1
9 9 9 0 9
9 9 9 9 0
0 9 9 9 9
9 0 9 9 9
9 9 0 9 9
9 9 9 0 9
9 9 9 9 0
2 4 3
4 2 3
2 4 1

样例输出 #1

6
9
7

提示

设有 n 个站点和m种赛车，换车限制为 k ，预测次数为 q 。

测试数据中100%的数据满足：

1 ≤m,n≤ 80 。

0≤k ≤3000 。

1≤q ≤200000 。

0≤ E( a,i ,j )≤ 10^6