|
Название задачи: Иванушка и царевна . |
 |
Условие
Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к столбу веревкой так, что веревка обмоталась вокруг царевны ровно 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] для нахождения в полученном графе кратчайшего пути из начальной вершины в конечную.
