P12864 [NERC 2020 Online] Optimum Server Location

世界顶级 IT 公司 Oondex 即将进驻 Lineland！在经历了多年烦人的"该服务在您所在区域不可用"错误提示后，Lineland 的居民终于能够收听最流行的音乐、观看最新的病毒视频，并享受 Oondex 提供的诸多服务。 Lineland 可以看作一条实数坐标轴。该地区有独特的网络资费标准：连接两个相距 $d$ 公里的服务器，建立一条吞吐量为 $t$ Mbit/s 的网络通道需要花费 $d \cdot t$ 美元。 为了提供更好的用户体验，Oondex 计划在 Lineland 部署 $n$ 台服务器。这些服务器将执行常规的数据处理任务，需要彼此之间进行密集的网络交互。同时，这些服务器还将为外部用户提供服务，通过 Lineland 已有的 $m$ 台特殊 CDN 服务器（内容分发服务器）进行内容分发。 Oondex 的分析师已经确定： - 对于每对服务器 $i$, $j$（$1 \leq i < j \leq n$），服务器 $i$ 和 $j$ 之间需要的吞吐量为 $d_{ij}$ Mbit/s - 对于每对服务器 $i$ 和 CDN 服务器 $k$（$1 \leq i \leq n$；$1 \leq k \leq m$），服务器 $i$ 和 CDN 服务器 $k$ 之间需要的吞吐量为 $c_{ik}$ Mbit/s 给定 CDN 服务器的位置 $a_k$（$1 \leq k \leq m$），确定 Oondex 服务器的部署位置 $x_i$（$1 \leq i \leq n$），使得部署成本最小。形式化地说，确定 $x_i$ 使得成本值 $v = \sum\limits_{1 \leq i < j \leq n} |x_i - x_j| \cdot d_{ij} + \sum\limits_{\substack{1 \leq i \leq n \\ 1 \leq k \leq m}} |x_i - a_k| \cdot c_{ik}$ 最小。允许多台服务器（包括 Oondex 服务器和 CDN 服务器）部署在同一位置。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 70$）——需要部署的 Oondex 服务器数量和已有的 CDN 服务器数量。 第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$（$0 \leq a_k \leq 10^6$）——现有 CDN 服务器的位置。 接下来的 $n$ 行，第 $i$ 行包含 $m$ 个整数 $c_{i1}, c_{i2}, \ldots, c_{im}$，其中 $c_{ik}$（$0 \leq c_{ik} \leq 50$）表示第 $i$ 台 Oondex 服务器与第 $k$ 台 CDN 服务器之间的吞吐量。 最后的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $d_{i1}, d_{i2}, \ldots, d_{in}$（$0 \leq d_{ij} \leq 50$；$d_{ij} = d_{ji}$；$d_{ii} = 0$），其中 $d_{ij}$ 表示第 $j$ 台 Oondex 服务器与第 $i$ 台 Oondex 服务器之间的吞吐量。

第一行输出值 $v$——部署 $n$ 台 Oondex 服务器的最小可能成本。 第二行输出 $n$ 个整数 $x_1, x_2, \ldots, x_n$，其中 $x_i$（$0 \leq x_i \leq 10^6$）表示第 $i$ 台 Oondex 服务器应该部署的位置。可以证明存在满足 $x_i$ 范围限制（范围和整数性）的最优解。

翻译由 DeepSeek V3 完成