17 стульев
Остап Бендер снова пытается получить причитающиеся драгоценности, но на этот раз они были запреты в шкатулке для открытия которой необходимо иметь n ключей. По закономерной случайности каждый из ключей был спрятан в одном из n стульев, распроданных на недавнем аукционе. После аукциона эти стулья были развезены в n городов.
И вот теперь Остап решился на новую безумную идею: заехать в каждый из городов и, провернув в каждом из них аферу, выкрасть необходимые ключи. Чтобы избежать конфликтов с недоброжелателями Остап не хочет больше одного раза появляться в каком либо городе. Также у Остапа есть список цен за проезд между каждой парой городов. Изначально Остап находится в городе под номером 1 и после посещения всех городов может незаметно скрыться из этой страны.
Помогите Остапу найти порядок посещения городов при котором ему потребуется потратить как можно меньше средств на странствия и тогда, возможно, он поделится с Вами добытыми бриллиантами.
Входные данные
Первая строка содержит количество городов n. Следующие n строк содержат по n целых неотрицательных чисел. j-ое число в i-ой строке означает стоимость проезда из города i в город j. Если a[ij] > 0, то проезд стоит a[ij] рублей, иначе это означает, что из города i в j невозможно проехать напрямую.
Количество городов не превышает числа, упоминаемого в названии задачи, а стоимость проезда между двумя городами не превышает 100.
Выходные данные
В первой строке выведите минимальную сумму денег, необходимую для посещения всех городов Остапом. В следующей строке выведите n чисел - порядок посещения городов, при котором эта сумма достигается.
Если добыть все ключи Остапу не удасться с соблюдением указанных в условии задачи условий, то выведите единственное число -1.