Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Кубок CBOSS

(Время: 1 сек. Память: 16 Мб Сложность: 52%)

В 2239 году команде-победителю Открытого кубка CBOSS (http://shade.msu.ru/~ejudge) достался весьма нетрадиционный приз - поездка по k самым красивым городам России. Так как в России красивых городов достаточно много, то победителям было предложено выбрать k городов из списка, содержащего n городов.

Для удобства занумеруем эти города целыми числами от 1 до n. Для каждого города известно ti - время, требующееся на осмотр его достопримечательностей. Также для каждой пары (i, j), 1 ≤ i, j ≤ n известно ai,j - время, которое требуется на проезд из i-ого города в j-ый. При этом может оказаться, что ai,j ≠ aj,i, но ai,i всегда равно нулю.

У студентов, входящих в команду-победитель, не так много времени на посещение красивых городов, ведь скоро у них сессия. Поэтому они хотят выбрать k городов и посетить их в таком порядке, чтобы затраты времени были минимальны. Разумеется, посещать один город несколько раз им неинтересно. Также они не хотят приезжать в город, не осматривая при этом его достопримечательности.

Напишите программу, находящую нужные k городов и порядок, в котором их нужно посетить.

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

Первая строка входного файла INPUT.TXT содержит целые числа n и k (1 ≤ n ≤ 7, 1 ≤ k ≤ n). Каждая из последующих n строк входного файла содержит по n целых чисел каждая: j-ое число (i + 1)-ой строки входного файла - это время, требуемое на проезд из i-ого города в j-ый (ai,j). Последняя строка входного файла содержит n целых чисел t1, …, tn.

Все числа во входном файле не превосходят 100. Все времена неотрицательны.

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

В первой строке выходного файла OUTPUT.TXT выведите минимальное время, которое потребуется для посещения k городов с учетом осмотра достопримечательностей. Во второй строке выходного файла выведите номера городов в порядке посещения, гарантирующем такое время.

Примеры

INPUT.TXTOUTPUT.TXT
14 3
0 3 2 1
8 0 6 5
1 2 0 4
5 6 7 0
1 2 3 4
10
3 1 4
24 4
0 3 2 1
8 0 6 5
1 2 0 4
5 6 7 0
1 2 3 4
18
3 1 4 2

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483