ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Такси для программистов

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
На часах 23:10. Только что закончилась очередная тренировка спортивных программистов мат-меха. Измождённые и грустные студенты медленно выползают из-за компьютеров. Одно согревает их: добрый тренер дядя Миша готов развезти студентов по домам на своём новеньком автомобиле. Хорошо, что пробок на дорогах нет. Плохо, что все студенты живут в разных частях города. Дядя Миша, будучи программистом, выделил и пронумеровал пять ключевых точек на карте Екатеринбурга: место тренировки (1), дом Кирилла (2), дом Ильи (3), дома Паши и Олега (4; они живут рядом) и свой дом (5). Теперь нужно составить оптимальный маршрут: он должен начинаться в точке 1, заканчиваться в точке 5 и быть минимальным по суммарному пройденному расстоянию. Более того, Илья не согласен быть последним, кого отвезут домой, поэтому точка 3 не может быть предпоследней в этом маршруте.

Исходные данные

На вход дана таблица расстояний между ключевыми точками. Она состоит из пяти строк и пяти столбцов. j-е число в i-й строке (1 ≤ i, j ≤ 5) — это расстояние между точками i и j. Все расстояния заданы в метрах и являются неотрицательными целыми числами, не превосходящими 10 000. Гарантируется, что расстояние от любой точки до самой себя равно нулю, и для любых двух точек расстояния туда и обратно совпадают. Также гарантируется, что длина прямого пути между любыми двумя точками не больше, чем длина любого пути между ними, проходящего через другую точку.

Результат

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

Пример

исходные данныерезультат
0 2600 3800 2600 2500
2600 0 5300 3900 4400
3800 5300 0 1900 4500
2600 3900 1900 0 3700
2500 4400 4500 3700 0
13500
1 2 3 4 5
Автор задачи: Михаил Рубинчик (подготовка — Олег Меркурьев)
Источник задачи: Уральская региональная командная олимпиада по программированию 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2005. Такси для программистов