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

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

Ограничения: время – 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` чисел – номера интересных мест в порядке посещения.

Пример ввода

3
1 2 3
0 10 1
10 0 1
1 1 0

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

6 2
1 3 2
Источник: neerc.ifmo.ru/school
loading