Задача F. Редкая птица
Задачу добавил: alef
Успешно сдано решений: 4
В отдел, где проходит практику Кеша, пришел один из заместителей директора с дискетой и очень попросил «сделать так, чтобы вот этот файл открывался в современных программах». Заняться поисками конвертера как раз предложили Кеше. Кеше удалось выяснить, что прямого способа преобразования не существует, понадобится проделать несколько шагов. Кроме того, на некоторых шагах преобразование будет происходить с потерей информации — и это значит, что придется вносить исправления вручную. Конечно, Кеше хочется ограничиться минимумом таких исправлений, и он хочет знать, какую цепочку преобразований ему лучше выбрать. Он составил таблицу, из которой можно узнать, сколько байтов ему придется исправлять при том или ином преобразовании. Итоговое количество исправляемых байтов определяется как сумма исправляемых на каждом шаге.Ваша задача — определить такую цепочку, при которой итоговое количество исправляемых байтов будет минимальным. Если существует несколько ответов, выведите любой.
Формат входного файла input.txt
Первая строка — два целых числа N и B через пробел; N (2 <= N <= 1000) — количество форматов, которые могут участвовать в преобразовании, B (2 <= B <= 10000) — количество байтов в файле, который нужно преобразовать. Считайте, что исходный формат файла имеет номер 1, целевой формат — номер N.
Каждая из следующих N строк описывает «цену» преобразования из формата #J (номер строки) во все остальные форматы и содержит N целых чисел Cjk (–1 <= Cjk <= B) через пробел. Если Cjk = –1, это означает, что конвертера из формата #J в формат #K не существует. Неотрицательное же число означает количество байтов, которые придется переправить вручную. Гарантируется, что все Cjj = 0.
Формат выходного файла output.txt
Первая строка — два целых числа P и S через пробел: P — количество форматов в цепочке преобразований (учитывая формат 1 и формат N), S — количество байтов, которые придется исправить вручную по ходу всех преобразований.
Вторая строка — P целых чисел через пробел — последовательность преобразований.
Пример входного файла
(числа выровнены для удобства восприятия, в оригинальном файле их разделяет один пробел)
7 712
0 2 17 26 5 39 -1
32 0 49 19 0 41 58
31 32 0 12 -1 15 30
-1 4 27 0 35 20 12
16 1 57 55 0 49 -1
37 -1 8 57 46 0 26
-1 -1 56 -1 -1 22 0
Пример выходного файла
4 33
1 2 4 7