Задача №3785. Задача коммивояжёра --- 2
На плоскости заданы координаты n (4 ≤ n ≤ 15) разных вершин.
Найти кратчайший замкнутый маршрут, начинающийся и заканчивающийся в 1-й вершине и посещающий все остальные вершины по одному разу. Разрешается (если так оказывается выгодно) «проезжать через вершину, не останавливаясь» (см. пример 1).
Длина маршрута считается как сумма длин составляющих его рёбер, длины отдельных рёбер считаются согласно обычной евклидовой метрике, как 
.
Первая строка содержит количество вершин n (4 ≤ n ≤ 15). Каждая из следующих n строк содержит по два разделённых пробелом числа с плавающей точкой — x- и y-координаты соответствующей вершины.
Первая строка должна содержать единственное число (с плавающей точкой) — найденную минимальную длину замкнутого тура. Вторая строка должна содержать перестановку чисел 2, 3, ..., N — порядок, в котором надо посещать эти вершины. Числа внутри второй строки должны разделяться одинарными пробелами.
Задача с такими ограничениями, по идее, должна решаться хоть методом ветвей и границ, хоть динамическим программированием по подмножествам. Но она, по идее, не должна решаться одними лишь отсечениями поиска с возвратом (backtracking), не пытающегося оценивать возможный диапазон длины ещё не построенной части пути.
4 0 0 2 0.2 7 0.7 5 0.5
1.40698258695692E+0001 2 4 3
5 1 0 4 4 3 2 4 0 1 1
1.24721359549995E+0001 5 3 2 4