题解\n\n#### 题目描述\n\n探险家需要依次巡查 $n$ 个哨站环路，每个环路是由若干个哨站按固定顺序连接而成的闭合多边形路径。第 $i$ 个环路包含 $m_i$ 个哨站，坐标以整数对给出。巡查第 $i$ 个环路时，需要选择一个哨站作为起点，按顺序驶过全部哨站并回到起点，巡查速度为 $v_i$。在两个环路之间转移时，乘坐飞行器沿直线移动，速度为 $u$。探险家可以自行决定巡查环路的顺序和每个环路的进入点，初始时可以任意选定第一条巡查环路的某个哨站作为出发点，完成所有环路后必须回到这个出发点。求完成全部巡查所需的最短总时间。\n\n#### 解题思路\n\n1. 计算周长：每个环路的周长由输入点按顺序连接形成闭合路径的长度决定。\n2. 枚举排列顺序：所有可能的巡查环路顺序，共 $n!$ 种情况。\n3. 动态规划：对每个排列顺序，通过动态规划确定每个环路的最佳进入点，使得飞行转移时间总和最小。\n4. 计算总时间：包括所有环路的巡查时间、环路间飞行转移时间和返回出发点的时间。\n\n#### 关键点\n\n- 周长计算：按输入点顺序计算闭合路径的总长度。\n- 动态规划状态：记录当前处理到第几个环路、当前环路的进入点和初始环路的进入点。\n- 时间计算：总时间为巡查时间加上飞行转移时间，其中飞行转移时间通过动态规划优化。\n\n#### 代码实现\n\n##### C++\n\ncpp\n#include <bits/stdc++.h>\nusing namespace std;\n\n// 定义点结构体\nstruct Point {\n int x, y;\n Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}\n // 重载小于运算符，用于排序\n bool operator<(const Point& other) const {\n if (x != other.x) return x < other.x;\n return y < other.y;\n }\n};\n\n// 定义环路结构体\nstruct Graph {\n double time; // 巡查该环路所需时间\n vector<Point> points; // 环路的所有哨站坐标\n};\n\nint main() {\n int n, x;\n cin >> n >> x; // 输入环路数量n和飞行器移动速度x（即u）\n vector<int> y(n); // 存储每个环路的巡查速度\n for (int i = 0; i < n; ++i) cin >> y[i];\n \n vector<Graph> graphs(n); // 存储所有环路信息\n \n // 处理每个环路的输入\n for (int i = 0; i < n; ++i) {\n int m;\n cin >> m; // 当前环路的哨站数量\n vector<Point> points; // 存储当前环路的哨站坐标\n \n // 输入所有哨站坐标\n for (int j = 0; j < m; ++j) {\n int a, b;\n cin >> a >> b;\n points.emplace_back(a, b);\n }\n \n // 计算环路的周长\n double perimeter = 0.0;\n for (int j = 0; j < m; ++j) {\n const Point& p1 = points[j];\n const Point& p2 = points[(j+1) % m]; // 循环连接首尾\n double dx = p1.x - p2.x;\n double dy = p1.y - p2.y;\n perimeter += sqrt(dx*dx + dy*dy); // 计算两点间距离\n }\n \n // 存储环路信息\n graphs[i].time = perimeter / y[i]; // 巡查时间 = 周长 / 巡查速度\n graphs[i].points = points;\n }\n\n vector<int> order(n); // 存储环路巡查顺序\n iota(order.begin(), order.end(), 0); // 初始顺序0,1,...,n-1\n double min_total = 1e18; // 初始化最小总时间为极大值\n \n // 枚举所有可能的环路巡查顺序\n do {\n // dp_prev记录状态：(当前哨站,初始哨站) -> 累计飞行时间\n map<pair<Point, Point>, double> dp_prev;\n \n // 初始化第一个环路的所有可能起点\n const auto& first_graph = graphs[order[0]];\n for (const Point& p : first_graph.points) {\n dp_prev[{p, p}] = 0.0; // 从p点开始，初始飞行时间为0\n }\n \n // 处理后续环路\n for (int k = 1; k < n; ++k) {\n const auto& curr_graph = graphs[order[k]];\n map<pair<Point, Point>, double> dp_curr; // 当前状态\n \n // 遍历前一状态\n for (const auto& entry : dp_prev) {\n const Point& prev_p = entry.first.first; // 前一个环路的进入点\n const Point& first_p = entry.first.second; // 初始哨站\n double prev_time = entry.second; // 累计飞行时间\n \n // 尝试当前环路的所有可能进入点\n for (const Point& new_p : curr_graph.points) {\n // 计算飞行转移时间\n double dx = prev_p.x - new_p.x;\n double dy = prev_p.y - new_p.y;\n double dist = sqrt(dx*dx + dy*dy);\n double move_time = dist / x; // 飞行时间 = 距离 / 飞行器速度\n \n // 更新状态\n auto key = make_pair(new_p, first_p);\n if (!dp_curr.count(key) || prev_time + move_time < dp_curr[key]) {\n dp_curr[key] = prev_time + move_time;\n }\n }\n }\n dp_prev = dp_curr;\n if (dp_prev.empty()) break; // 无可行路径则跳过\n }\n \n if (dp_prev.empty()) continue; // 无解情况\n \n // 计算返回初始哨站的时间\n double min_move = 1e18;\n for (const auto& entry : dp_prev) {\n const Point& last_p = entry.first.first; // 最后一个环路的进入点\n const Point& first_p = entry.first.second; // 初始哨站\n double dx = last_p.x - first_p.x;\n double dy = last_p.y - first_p.y;\n double dist = sqrt(dx*dx + dy*dy);\n double total_move = entry.second + dist / x; // 累计飞行时间 + 返回时间\n if (total_move < min_move) {\n min_move = total_move;\n }\n }\n \n // 计算总时间：飞行转移时间 + 所有环路的巡查时间\n double total_time = min_move;\n for (int i : order) {\n total_time += graphs[i].time;\n }\n \n // 更新最小总时间\n if (total_time < min_total) {\n min_total = total_time;\n }\n } while (next_permutation(order.begin(), order.end())); // 尝试所有排列顺序\n \n // 输出结果，保留12位小数\n cout << fixed << setprecision(12) << min_total << endl;\n return 0;\n}\n\n\n##### Python\n\npython\nimport itertools\nimport math\n\nclass Point:\n def __init__(self, x, y):\n self.x = x\n self.y = y\n \n # 定义哈希函数，用于作为字典键\n def __hash__(self):\n return hash((self.x, self.y))\n \n # 定义相等比较\n def __eq__(self, other):\n return self.x == other.x and self.y == other.y\n \n # 定义小于比较，用于排序\n def __lt__(self, other):\n if self.x != other.x:\n return self.x < other.x\n return self.y < other.y\n\ndef main():\n import sys\n input = sys.stdin.read().split()\n ptr = 0\n n = int(input[ptr])\n x = int(input[ptr+1]) # 飞行器移动速度（即u）\n ptr += 2\n y = list(map(int, input[ptr:ptr+n])) # 各个环路的巡查速度\n ptr += n\n graphs = []\n \n # 读取每个环路的数据\n for i in range(n):\n m = int(input[ptr])\n ptr += 1\n points = []\n for j in range(m):\n a = int(input[ptr])\n b = int(input[ptr+1])\n ptr += 2\n points.append(Point(a, b))\n \n # 计算周长\n perimeter = 0.0\n for j in range(m):\n p1 = points[j]\n p2 = points[(j+1)%m] # 循环连接首尾\n dx = p1.x - p2.x\n dy = p1.y - p2.y\n perimeter += math.hypot(dx, dy) # 计算两点间距离\n \n # 存储环路信息\n time_i = perimeter / y[i] # 巡查时间 = 周长 / 巡查速度\n graphs.append({'time': time_i, 'points': points})\n \n min_total = float('inf')\n \n # 尝试所有可能的环路巡查顺序\n for order in itertools.permutations(range(n)):\n first_points = graphs[order[0]]['points']\n dp_prev = {}\n \n # 初始化第一个环路的所有可能起点\n for p in first_points:\n key = (p, p)\n dp_prev[key] = 0.0 # 从p点开始，初始飞行时间为0\n \n # 处理后续环路\n for k in range(1, n):\n curr_graph = graphs[order[k]]\n curr_points = curr_graph['points']\n dp_curr = {}\n \n # 遍历前一状态\n for (prev_p, first_p) in dp_prev:\n prev_time = dp_prev[(prev_p, first_p)]\n \n # 尝试当前环路的所有可能进入点\n for new_p in curr_points:\n dx = prev_p.x - new_p.x\n dy = prev_p.y - new_p.y\n dist = math.hypot(dx, dy)\n move_time = dist / x # 飞行时间 = 距离 / 飞行器速度\n \n # 更新状态\n key = (new_p, first_p)\n total_time = prev_time + move_time\n if key not in dp_curr or total_time < dp_curr.get(key, float('inf')):\n dp_curr[key] = total_time\n \n dp_prev = dp_curr\n if not dp_prev:\n break # 无可行路径则跳过\n \n if not dp_prev:\n continue # 无解情况\n \n # 计算返回初始哨站的时间\n min_move = float('inf')\n for (last_p, first_p) in dp_prev:\n dx = last_p.x - first_p.x\n dy = last_p.y - first_p.y\n dist = math.hypot(dx, dy)\n total_move = dp_prev[(last_p, first_p)] + dist / x # 累计飞行时间 + 返回时间\n if total_move < min_move:\n min_move = total_move\n \n # 计算总时间：飞行转移时间 + 所有环路的巡查时间\n total_time = sum(graphs[i]['time'] for i in order) + min_move\n \n # 更新最小总时间\n if total_time < min_total:\n min_total = total_time\n \n # 输出结果，保留12位小数\n print("{0:.12f}".format(min_total))\n\nif __name__ == "__main__":\n main()\n\n\n##### Java\n\njava\nimport java.util.*;\nimport java.awt.Point;\n\nclass Graph {\n double time; // 巡查该环路所需时间\n List<Point> points; // 环路的哨站坐标\n\n Graph(double time, List<Point> points) {\n this.time = time;\n this.points = points;\n }\n}\n\npublic class Main {\n // 定义状态键类，包含当前哨站和初始哨站\n static class Pair {\n Point a;\n Point b;\n Pair(Point a, Point b) {\n this.a = a;\n this.b = b;\n }\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (o == null || getClass() != o.getClass()) return false;\n Pair pair = (Pair) o;\n return a.equals(pair.a) && b.equals(pair.b);\n }\n @Override\n public int hashCode() {\n return Objects.hash(a, b);\n }\n }\n\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int n = sc.nextInt(); // 环路数量\n int x = sc.nextInt(); // 飞行器移动速度（即u）\n int[] y = new int[n]; // 每个环路的巡查速度\n for (int i = 0; i < n; i++) y[i] = sc.nextInt();\n \n List<Graph> graphs = new ArrayList<>(); // 存储所有环路信息\n \n // 读取每个环路的数据\n for (int i = 0; i < n; i++) {\n int m = sc.nextInt(); // 当前环路的哨站数量\n List<Point> points = new ArrayList<>();\n for (int j = 0; j < m; j++) {\n int a = sc.nextInt();\n int b = sc.nextInt();\n points.add(new Point(a, b));\n }\n \n // 计算周长\n double perimeter = 0.0;\n for (int j = 0; j < m; j++) {\n Point p1 = points.get(j);\n Point p2 = points.get((j + 1) % m); // 循环连接首尾\n double dx = p1.x - p2.x;\n double dy = p1.y - p2.y;\n perimeter += Math.sqrt(dx * dx + dy * dy); // 计算两点间距离\n }\n \n // 存储环路信息\n graphs.add(new Graph(perimeter / y[i], points)); // 巡查时间 = 周长 / 巡查速度\n }\n \n List<Integer> order = new ArrayList<>();\n for (int i = 0; i < n; i++) order.add(i);\n double minTotal = Double.MAX_VALUE;\n \n // 生成所有巡查顺序的排列\n do {\n Map<Pair, Double> dpPrev = new HashMap<>();\n List<Point> firstPoints = graphs.get(order.get(0)).points;\n \n // 初始化第一个环路的所有可能起点\n for (Point p : firstPoints) {\n Pair key = new Pair(p, p);\n dpPrev.put(key, 0.0); // 从p点开始，初始飞行时间为0\n }\n \n // 处理后续环路\n for (int k = 1; k < n; k++) {\n Graph currGraph = graphs.get(order.get(k));\n List<Point> currPoints = currGraph.points;\n Map<Pair, Double> dpCurr = new HashMap<>();\n \n // 遍历前一状态\n for (Map.Entry<Pair, Double> entry : dpPrev.entrySet()) {\n Point prevP = entry.getKey().a; // 前一个环路的进入点\n Point firstP = entry.getKey().b; // 初始哨站\n double prevTime = entry.getValue();\n \n // 尝试当前环路的所有可能进入点\n for (Point newP : currPoints) {\n double dx = prevP.x - newP.x;\n double dy = prevP.y - newP.y;\n double dist = Math.sqrt(dx * dx + dy * dy);\n double moveTime = dist / x; // 飞行时间 = 距离 / 飞行器速度\n \n // 更新状态\n Pair key = new Pair(newP, firstP);\n double totalTime = prevTime + moveTime;\n if (!dpCurr.containsKey(key) || totalTime < dpCurr.get(key)) {\n dpCurr.put(key, totalTime);\n }\n }\n }\n dpPrev = dpCurr;\n if (dpPrev.isEmpty()) break; // 无可行路径则跳过\n }\n \n if (dpPrev.isEmpty()) continue; // 无解情况\n \n // 计算返回初始哨站的时间\n double minMove = Double.MAX_VALUE;\n for (Map.Entry<Pair, Double> entry : dpPrev.entrySet()) {\n Point lastP = entry.getKey().a; // 最后一个环路的进入点\n Point firstP = entry.getKey().b; // 初始哨站\n double dx = lastP.x - firstP.x;\n double dy = lastP.y - firstP.y;\n double dist = Math.sqrt(dx * dx + dy * dy);\n double totalMove = entry.getValue() + dist / x; // 累计飞行时间 + 返回时间\n if (totalMove < minMove) {\n minMove = totalMove;\n }\n }\n \n // 计算总时间：飞行转移时间 + 所有环路的巡查时间\n double totalTime = minMove;\n for (int i : order) {\n totalTime += graphs.get(i).time;\n }\n \n // 更新最小总时间\n if (totalTime < minTotal) {\n minTotal = totalTime;\n }\n } while (nextPermutation(order)); // 尝试所有排列顺序\n \n // 输出结果，保留12位小数\n System.out.printf("%.12f\n", minTotal);\n }\n \n // 生成下一个排列\n static boolean nextPermutation(List<Integer> a) {\n int i = a.size() - 2;\n while (i >= 0 && a.get(i) >= a.get(i + 1)) i--;\n if (i < 0) return false;\n int j = a.size() - 1;\n while (a.get(j) <= a.get(i)) j--;\n Collections.swap(a, i, j);\n Collections.reverse(a.subList(i + 1, a.size()));\n return true;\n }\n}\n