ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102892
Тема:    [ Кратчайшие пути в графах ]
Сложность: 3+
Классы:
Название задачи: Иванушка и царевна .
В корзину
Прислать комментарий

Условие

Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к столбу веревкой так, что веревка обмоталась вокруг царевны ровно I раз по часовой стрелке. Иванушка хочет освободить царевну и взять ее в жены. Проблема заключается в том, что плавать в болоте невозможно и ему приходится прыгать по кочкам. При каждом таком прыжке за ноги Иванушки зацепляется определенное количество зеленых водорослей. 

Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну).

Требуется определить такой маршрут движения Иванушки, при котором за его ноги зацепится минимально возможное количество водорослей.

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

Первая строка входного файла содержит три целых числа: N – количество кочек в болоте (3 ≤ N ≤ 10), I – количество оборотов веревки (1 ≤ I ≤ 6) и S – номер кочки, на которой в начальный момент стоит Иванушка (1 ≤ S ≤ N). Каждая из следующих N строк содержит вещественные координаты одной из кочек, записанные через пробел. Известно, что никакой отрезок, соединяющий две кочки, не проходит через центр болота, имеющий по соглашению координаты (0, 0).

В следующих N строках записана матрица N × N, составленная из вещественных чисел. Число в i-й строке и j-м столбце этой матрицы означает количество водорослей, цепляющихся за ноги Иванушки при прыжке с i-й кочки на j-ю.

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

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

Пример входного файла

3 1 1
-1 0
0 1
1 -2
0 1 1
1 0 1
1 1 0

Пример выходного файла

3.00
1 3 2 1

Решение

Скачать архив тестов и решений

Текущее состояние Иванушки в процессе прыжков определяется номером кочки, на которой он находится, и количеством оборотов веревки вокруг царевны. При этом количество оборотов мы можем считать целым числом из диапазона [-10, 10], поскольку его дробная часть однозначно восстанавливается по номеру кочки. Построим граф, вершины которого будут соответствовать возможным состояниям Иванушки, т.е. парам (номер кочки, число оборотов), а ребра – допустимым переходам между ними (т.е. прыжкам Иванушки с одной кочки на другую). Каждому ребру припишем вес, равный количеству зеленых водорослей, цепляющихся за ноги Иванушки при соответствующем прыжке.
Теперь можно воспользоваться алгоритмом Дейкстры [Липский 88, п. 3.3] для нахождения в полученном графе кратчайшего пути из начальной вершины в конечную.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 3
Название Алгоритмы на графах
Задача
Номер 9

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .