Задача №111623. Продавец
На плоскости заданы координаты n (4 ≤ n ≤ 20) разных вершин.
Найти кратчайший замкнутый маршрут, начинающийся и заканчивающийся в 1-й вершине и посещающий все остальные вершины по одному разу. Разрешается (если так оказывается выгодно) «проезжать через вершину, не останавливаясь» (см. пример 1).
Длина маршрута считается как сумма длин составляющих его рёбер, длины отдельных рёбер считаются согласно обычной евклидовой метрике, как 
.
Первая строка содержит количество вершин n (4 ≤ n ≤ 20). Каждая из следующих n строк содержит по два разделённых пробелом числа с плавающей точкой — x- и y-координаты соответствующей вершины.
Первая строка должна содержать единственное число (с плавающей точкой) — найденную минимальную длину замкнутого тура. Вторая строка должна содержать перестановку чисел 2, 3, ..., N — порядок, в котором надо посещать эти вершины. Числа внутри второй строки должны разделяться одинарными пробелами.
В этой задаче есть 3 подзадачи
- Тест 1 (0 баллов). Это тест из условия
- Тесты 2-25 (40 баллов). В этой подзадаче \(N \leq 12\)
- Тесты 26-63 (60 баллов). В этой подзадаче дополнительные ограничения отсутствуют
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