← 返回题目列表

AtCoder · awc0017_e

E. 配送路线优化

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥是一名送货司机。总共有 N 与今天的交货相关的位置,每个编号从 1 to N.位置 1 为配送中心(同时作为出发点和返回点),地点 2 通过 N 是包裹必须投递的目的地。

每个地点 i 位于坐标处 (X_i, Y_i) 在二维平面上。请注意,不同的位置可能共享相同的坐标。

高桥计划从配送中心(位置 1),访问所有目的地(地点 2 通过 N)每次恰好一次,然后返回配送中心(位置 1)。具体来说,他选择了一个排列 (p_1, p_2, \ldots, p_{N-1}) of (2, 3, \ldots, N) 并按以下顺序行驶:

1 \to p_1 \to p_2 \to \cdots \to p_{N-1} \to 1

高桥的送货卡车从坐标直接行驶的燃油费用 (a, b) 到坐标 (c, d) 计算如下 (a - c)^2 + (b - d)^2.

游览路线的总燃料成本是沿路线每对连续地点之间的旅行成本之和。具体来说,上述游览线路的燃油费用为:

\mathrm{dist}(1, p_1) + \sum_{k=1}^{N-2} \mathrm{dist}(p_k, p_{k+1}) + \mathrm{dist}(p_{N-1}, 1)

其中 \mathrm{dist}(i, j) = (X_i - X_j)^2 + (Y_i - Y_j)^2 表示从该地点出发的交通费用 i 到位置 j.

高桥希望通过自由选择访问目的地的顺序来最小化游览路线的总燃料成本。直接沿着游览路线进行旅行;他不能沿途经过其他地点或任意坐标。

求最小燃料成本。

约束

  • 2 \leq N \leq 16
  • -1000 \leq X_i \leq 1000 \quad (1 \leq i \leq N)
  • -1000 \leq Y_i \leq 1000 \quad (1 \leq i \leq N)
  • 所有输入值均为整数

输入

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
  • 第一行包含一个整数 N 代表位置的数量。
  • 行 2 通过 N + 1 给出每个位置的坐标。
  • 线 1 + i 包含 x- 坐标 位置 X_i 和 y- 坐标 位置 Y_i 的位置 i,用空格分隔。

输出

在单行上以整数形式输出旅游路线的最低总燃料成本。


示例输入 1

2
0 0
1 1

示例输出 1

4

示例输入 2

4
0 0
1 0
1 1
0 1

示例输出 2

4

示例输入 3

5
0 0
3 0
3 4
-1 3
0 3

示例输出 3

46