AT_m_solutions2020_e M's Solution

新 AtCoder 市有着类似无限扩展的棋盘结构，如下描述： - 市中心坐落着一座钟楼，其坐标为 $ (0, 0) $。 - 钟楼所在的东西向大路被称作「东西大路」，在二维坐标系中表示为 $ x $ 轴。 - 除此之外，还有无数条平行于东西大路的道路，相距均为 1。这些道路对应于 $ y = (非零整数) $ 的直线。 - 钟楼所在的南北向大路被称作「南北大路」，在二维坐标系中表示为 $ y $ 轴。 - 另外，同样有无数条平行于南北大路的道路，相隔距离均为 1，这些道路对应于 $ x = (非零整数) $ 的直线。 在新 AtCoder 市中，存在 $ N $ 个村落。第 $ i $ 个村落位于坐标 $ (X_i, Y_i) $ 的十字路口上，人口为 $ P_i $。所有市民皆居住于这些村落中。 **目前，铁路仅有两条：一条沿东西大路延伸，另一条沿南北大路延伸。** 然而，市长 M 君认为这样的布局给出行带来了不便，因此计划在 $ K $ 条道路上增设铁路，使铁路无限延伸。 定义每个市民到最近铁路线路的距离为「步行距离」。我们的目标是通过合理选址新修铁路，使得所有市民的步行距离之和 $ S $ 达到最小。 请计算，对于每一个 $ K = 0, 1, 2, \dots, N $，修建铁路后 $ S $ 的最小值是多少？

输入格式如下： > $ N $ $ X_1 $ $ Y_1 $ $ P_1 $ $ X_2 $ $ Y_2 $ $ P_2 $ $\ldots$ $ X_N $ $ Y_N $ $ P_N $

请输出 $ N+1 $ 行。第 $ i $ 行（$ i = 1, \ldots, N+1 $）表示当 $ K = i - 1 $ 时 $ S $ 的最小值。每个最小值应为整数。

- $ 1 \leq N \leq 15 $ - $ -10\ 000 \leq X_i \leq 10\ 000 $ - $ -10\ 000 \leq Y_i \leq 10\ 000 $ - $ 1 \leq P_i \leq 1\ 000\ 000 $ - 所有 $ N $ 个村落的位置 $ (X_i, Y_i) $ 都不同 - 输入均为整数 ### 样例解释 1. 对于 $ K = 0 $，村落 1、2、3 的居民分别需要步行 1、3、1 个单位到达铁道。所以，总步行距离 $ S = 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900 $。 2. 当 $ K = 1 $ 时，在东西大路向北 4 单位的地方修建铁路，村落 1、2、3 的居民步行距离分别为 1、1、0。此时 $ S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900 $。对于其他方案，$ S $ 都无法小于 900。 3. 当 $ K = 2 $ 时，在南北大路东 1 和 3 单位处修建铁路，所有居民的步行距离均为 0，因此 $ S = 0 $。同样地，$ K = 3 $ 时 $ S = 0 $ 也是最优解。 下图展示了 $ K = 0, 1, 2 $ 三种情况下最优的铁道铺设方案，蓝色代表铺设铁路的道路。  **本翻译由 AI 自动生成**