SP26958 SPACESHIP - Spaceship

在未来的世界中，你已经搬到了太空殖民地，并将使用一种可以在三维空间中飞行的飞碟作为交通工具。你的任务是为 $N$ 台电脑购买配件。每台电脑需要 3 个部分：显示器、键盘和 CPU。由于某个商店可能无法提供足够的配件来组装 $N$ 台电脑，并且预算也是有限的，你需要为飞碟设计一个导航系统，以最小化总的导航成本。你已经知道所有 $M$ 个商店的确切坐标，以及每个商店提供的配件数量。假设从一个商店到另一个商店的路径上没有障碍物，因此可以直接飞过去，并且飞碟有无限的存储空间，商店的零件也是免费的。只要收集到所有需要的零件，旅程就结束。 假设商店 A 的坐标为 $(X1, Y1, Z1)$，商店 B 的坐标为 $(X2, Y2, Z2)$，则从商店 A 到��店 B 的导航成本计算公式为：$(X1 - X2)^2 + (Y1 - Y2)^2 + (Z1 - Z2)^2$。

第一行是一个整数 $N$：表示需要组装的电脑套数。 第二行包含三个整数 $X$、$Y$、$Z$：表示飞碟的初始坐标 $(X, Y, Z)$。 第三行是一个整数 $M$：表示殖民地中的商店总数。 接下来的 $2M$ 行中，每两行提供一个商店的信息。 第一行包含三个整数 $Xi$、$Yi$、$Zi$，表示商店的坐标 $(Xi, Yi, Zi)$。 第二行包含三个整数 $Mi$、$Ki$、$Ci$，分别表示该商店可提供的显示器、键盘和 CPU 的数量。 可以保证所有商店的配件总数足够组装出 $N$ 台电脑。

输出一行，表示从初始位置到结束旅程的最小导航成本。

$$1 \leq N \leq 20$$ $$0 \leq X, Y, Z, Xi, Yi, Zi \leq 500$$ $$1 \leq M \leq 10$$ $$0 \leq Mi, Ki, Ci \leq 20$$ **本翻译由 AI 自动生成**