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)$ 需要的时间 接下来的 $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$ 感谢 @frankchenfu、@yuhaocheng 提供的翻译

题目描述

PMP is getting a warrior. He is practicing a lot, but the results are not acceptable yet. This time instead of programming contests, he decided to compete in a car racing to increase the spirit of victory. He decides to choose a competition that also exhibits algorithmic features. AlgoRace is a special league of car racing where different teams compete in a country of $ n $ cities. Cities are numbered $ 1 $ through $ n $ . Every two distinct cities in the country are connected with one bidirectional road. Each competing team should introduce one driver and a set of cars. The competition is held in $ r $ rounds. In $ i $ -th round, drivers will start at city $ s_{i} $ and finish at city $ t_{i} $ . Drivers are allowed to change their cars at most $ k_{i} $ times. Changing cars can take place in any city in no time. One car can be used multiple times in one round, but total number of changes should not exceed $ k_{i} $ . Drivers can freely choose their path to destination. PMP has prepared $ m $ type of purpose-built cars. Beside for PMP’s driving skills, depending on properties of the car and the road, a car traverses each road in each direction in different times. PMP Warriors wants to devise best strategies of choosing car and roads in each round to maximize the chance of winning the cup. For each round they want to find the minimum time required to finish it.

输入输出格式

输入格式

The first line contains three space-separated integers $ n,m,r $ ( $ 2<=n<=60,1<=m<=60,1<=r<=10^{5} $ ) — the number of cities, the number of different types of cars and the number of rounds in the competition, correspondingly. Next $ m $ sets of $ n×n $ matrices of integers between $ 0 $ to $ 10^{6} $ (inclusive) will follow — describing the time one car requires to traverse different roads. The $ k $ -th integer in $ j $ -th line of the $ i $ -th set is the time that $ i $ -th car requires to traverse the road from $ j $ -th city to $ k $ -th city. These matrices are not necessarily symmetric, but their diagonal is always zero. Next $ r $ lines contain description of the rounds. The $ i $ -th of these lines contains space-separated integers $ s_{i},t_{i},k_{i} $ ( $ 1<=s_{i},t_{i}<=n,s_{i}≠t_{i},0<=k_{i}<=1000 $ ) — the number of starting city, finishing city and the number of possible car changes in $ i $ -th round, correspondingly.

输出格式

For each round you should print the minimum required time to complete the round in a single line.

输入输出样例

输入样例 #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

说明

In the first sample, in all rounds PMP goes from city #1 to city #2, then city #3 and finally city #4. But the sequences of types of the cars he uses are (1, 2, 1) in the first round and (1, 2, 2) in the second round. In the third round, although he can change his car three times, he uses the same strategy as the first round which only needs two car changes.