题解

题目描述

小美在平面上画了 $n$ 个封闭图形，每个图形由若干点描述。激光打印机需要按顺序打印这些图形，打印每个图形时需移动激光发射器到该图形的一个点，并以特定速度绘制。所有图形打印完毕后需返回初始点。求完成所有打印的最短时间。

解题思路

1. 计算周长：每个图形的周长由输入点按顺序连接形成闭合路径的长度决定。
2. 枚举排列顺序：所有可能的图形打印顺序，共 $n!$ 种情况。

题目内容

小美在纸上面了 $n$ 个封闭图形，编号为 $1,2,...,n$，第 $i$ 个图形由 $m_i$ 个点描述，他正在捣鼓他的激光打印机打印出这些图形。

这个打印机可以在平面上连续的移动打印，依靠激光发射器实现，激光发射器初始可以位于平面上的任意一个点 $S_0$ ，随后，由你确定打印顺序，按以下步骤依次打印这 $n$ 个图形：

• 记当前打印的图形编号为 $i$

• 将激光发射器以 $x$ 个单位长度每秒的速度移动到 $m_i$ 点中的其中一个(任选)，作为起始端点 $S_i$ ；