题目分析

题目本质

本题要求从 $(0,0)$ 出发，遍历 $n$ 个点，每个点都访问一次，问最短路程是多少。这是经典的旅行商问题（TSP, Traveling Salesman Problem），区别在于无需返回原点。

算法思路

由于 $n$ 很小（$n\leq15$），可采用状态压缩动态规划解决：

题目内容

在一个二维平面中，有 $n$ 个营地坐标点。一个人 $(0,0)$ 点处出发去达所有营地进行营救搜寻，问至少要走多少距离?

输入描述

第一行有一个整数，表示坐标点的数量 $n$ 。

第 $2$ 到第 $(n+1)$ 行，每行两个实数，第 $(i+1)$ 行的实数分别表示第 $i$ 个营地坐标点的横纵坐标 $xi,yi$ 。

$1≤n≤15,∣xi∣,∣yi∣≤200$ 。

输出描述

输出一个实数，表示要走的最少距离，保留 $2$ 位小数。

样例1

输入

3
1 3
2 5
0 9

输出

9.87