← 返回题目列表

Codeforces · 187/B

B. 算法竞赛

中文机器翻译题面 查看原题

PMP 正在获得一名战士。他练习了很多,但结果还不能让人接受。这次他没有参加编程比赛,而是参加了赛车比赛,以增加胜利的精神。他决定选择一个也展示算法特征的竞赛。

AlgoRace 是一个特殊的赛车联盟,不同的车队在一个由 n 个城市组成的国家进行比赛。城市编号为 1 到 n。该国每两个不同的城市都有一条双向道路连接。每个参赛队应引进一名车手和一组赛车。

比赛分r轮进行。第i轮比赛中,车手将从城市si出发,在城市ti结束。驾驶员最多可以换车 ki 次。任何城市都可以立即换车。一辆车在一轮中可以多次使用,但总更换次数不得超过 ki。驾驶员可以自由选择到达目的地的路径。

PMP准备了m型专用汽车。除了PMP的驾驶技巧之外,根据汽车和道路的特性,汽车在不同的时间向各个方向穿过每条道路。

PMP Warriors 希望制定每轮选择汽车和道路的最佳策略,以最大限度地提高赢得奖杯的机会。对于每一轮,他们都想找到完成它所需的最短时间。

输入

第一行包含三个空格分隔的整数 n, m, r (2 ≤ n ≤ 60, 1 ≤ m ≤ 60, 1 ≤ r ≤ 105)——分别对应城市数量、不同类型赛车数量和比赛轮数。

接下来是 m 组 n × n 0 到 106(含)之间的整数矩阵 — 描述一辆车穿过不同道路所需的时间。第i组的第j行中的第k个整数是第i辆车从第j个城市到第k个城市穿过道路所需的时间。这些矩阵不一定是对称的,但它们的对角线始终为零。

接下来的 r 行包含回合的描述。这些行的第 i 行包含空格分隔的整数 si, ti, ki (1 ≤ si, ti ≤ n, si ≠ ti, 0 ≤ ki ≤ 1000) — 相应地,起始城市、结束城市的数量以及第 i 轮中可能的汽车更换数量。

输出

对于每一轮,您应该在一行中打印完成该轮所需的最短时间。

示例

输入 #1

4 2 3
0 1 5 6
2 0 3 6
1 3 0 1
6 6 7 0
0 3 5 6
2 0 1 6
1 3 0 2
6 6 7 0
1 4 2
1 4 1
1 4 3

输出 #1

3
4
3

输入 #2

4 2 3
0 7 3 3
8 0 10 5
1 1 0 4
8 9 2 0
0 3 3 9
7 0 4 9
3 8 0 4
4 8 9 0
2 3 3
2 1 3
1 2 2

输出 #2

4
5
3

注意

在第一个样本中,在所有轮次中,PMP 从城市 #1 到城市 #2,然后是城市 #3,最后是城市 #4。但他使用的车型顺序第一轮是(1,2,1),第二轮是(1,2,2)。第三回合,虽然他可以换车三次,但他采用的策略与第一回合相同,只需要换车两次。