题目分析

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

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

P3421.第2题-营救搜寻

1000ms

Difficulty: 6

所属公司 : 钉钉

算法与标签>动态规划

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

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

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

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

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

输入

输出

9.87

输入

预期输出（选填）