07/04/2025 00:35:15

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2074. Хоббит, или Туда и обратно

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Бильбо вернулся домой после необычного путешествия и решил написать об этом книгу с названием "Алая книга Западных пределов". Во время своего путешествия он побывал в пещерах под Мглистым хребтом, в тюрьме эльфов Лихолесья, встретил дракона на Одинокой горе и побывал во многих переделках.

Всего Бильбо побывал в

$n$ интересных местах. Все интересные места, а также его дом находятся на одной прямой. Его дом находится на прямой в точке с координатой

$0$ , а

$i$ -ое интересное место удалено от дома Бильбо на

$x_i$ километров. Между каждой парой интересных мест

$i$ и

$j$ есть скрытый путь, который не проходит через другие интересные места. Длина этого пути равна

$|x_j\ -\ x_i|$ , а опасность равна

$c_{i,j}$ . Между

$i$ -ым интересным местом и домом также есть скрытый путь, длина которого –

$x_i$ , а опасность –

$0$ .

Бильбо побывал ровно один раз в каждом интересном месте и затем вернулся домой. Известно, что среди всех возможных путешествий Бильбо выбрал кратчайшее, а среди кратчайших – самое безопасное путешествие. Помогите Бильбо узнать длину путешествия, его опасность и порядок посещения интересных мест.

Первая строка входного файла содержит одно целое число

$n$ (

$1\ ≤\ n\ ≤\ 1000$ ) – количество интересных мест. Во второй строке дано

$n$ чисел

$x_i$ (

$1\ ≤\ x_i\ ≤\ 10^9$ ), где

$x_i$ – удаленность

$i$ -того места от дома Бильбо в километрах. Все

$x_i$ различны.

В каждой из следующих

$n$ строчек содержится по

$n$ чисел.

$j$ -ое число в

$i$ -ой строчке –

$c_{i,j}$ , опасность скрытого пути между местами

$i$ и

$j$ (

$0\ ≤\ c_{i,j}\ ≤\ 10^6$ ,

$c_{i,j}\ =\ c_{j,i}$ ,

$c_{i,i}\ =\ 0$ ).

В первой строке выведите два числа – длину и опасность пути Бильбо. Во второй строке выведите

$n$ чисел – номера интересных мест в порядке посещения.

Пример ввода

Пример вывода

6 2
1 3 2

Источник: neerc.ifmo.ru/school