Олимпиадный тренинг

Задача . B. Алгогонки


Задача

Темы: дп кратчайшие пути *1800

PMP готовится стать воином. Он много тренируется, но результаты пока не очень. На этот раз вместо контестов по программированию он решил состязаться в гонках, чтобы поднять дух победы. Он решил выбрать соревнование, которое помимо прочего использует его алгоритмические навыки.

AlgoRace — особая лига гонщиков, где разные команды соревнуются в стране с n городами. Города пронумерованы от 1 до n. Каждые два различных города страны связаны друг с другом двусторонней дорогой. Каждая команда должна представить на соревновании одного водителя и набор автомобилей.

Соревнование проводится в r раундов. На i-м раунде водители стартуют в городе si, а финишируют в городе ti. В течении этого раунда водителям разрешено менять автомобили не более ki раз. Поменять автомобиль можно в любом городе, это действие не занимает времени. Один автомобиль можно использовать несколько раз за раунд, но общее число пересадок не должно превышать ki. Водители могут свободно выбирать свой путь к месту назначения.

PMP-воин подготовил m типов специально сконструированных автомобилей. Кроме того, PMP водит по-разному в зависимости от свойств автомобиля и дороги, следовательно, автомобиль проезжает разные дороги (или одну дорогу в разных направлениях) за разное время.

PMP-воин хочет разработать лучшие стратегии выбора автомобилей и дорог в каждом раунде, чтобы максимизировать шансы выиграть кубок. Для каждого раунда надо найти минимальное время, необходимое для его прохождения.

Входные данные

Первая строка содержит три целых числа, разделенных пробелом n, m, r (2 ≤ n ≤ 60, 1 ≤ m ≤ 60, 1 ≤ r ≤ 105) — количество городов, количество различных типов машин и количество раундов в соревновании, соответственно.

Затем последуют m матриц размера n × n, состоящих из целых чисел от 0 до 106 (включительно), описывающие время, необходимое для одной машины для того, чтобы проехать разные дороги. Целое число, которое следует k-ым в j-ой строке i-й матрицы, обозначает время, за которое i-ый автомобиль проедет дорогу из j-го города в k-ый город. Заданные матрицы необязательно симметричны, но их диагональ всегда нулевая.

В следующих r строках содержатся описания раундов, i-ая из них содержит разделенные пробелом целые числа si, ti, ki (1 ≤ si, ti ≤ n, si ≠ ti, 0 ≤ ki ≤ 1000) — номер города-старта, номер города-финиша и количество допустимых пересадок в i-ом раунде, соответственно.

Выходные данные

Ваша задача — для каждого раунда вывести на отдельной строке минимальное время, необходимое для прохождения раунда.

Примечание

В первом примере во всех раундах PMP проезжает от города #1 до города #2, затем до города #3 и наконец до города #4. Но последовательность типов машин, которые он использует, в первом раунде (1, 2, 1), а во втором раунде (1, 2, 2). В третьем раунде он может поменять машину три раза. Здесь PMP использует такую же стратегию как и в первом раунде, меняя машину только два раза.


Примеры
№Входные данныеВыходные данные
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 
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 
4
5
3

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет