题目详情题解（0）讨论（0）提交记录（0）

AT_abc210_d.[ABC210D] National Railway

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥王国可以用一个 $ H $ 行 $ W $ 列的网格表示。用 $ (i, j) $ 表示从北边数第 $ i $ 行、从西边数第 $ j $ 列的格子。

最近，王国内要求修建铁路的公民呼声越来越高，国王高桥君别无选择，必须修建一条铁路。铁路的修建包含以下两个阶段：

  • 首先，选择两个不同的格子，并在每个格子上修建一个车站。在格子 $ (i, j) $ 上修建车站需要花费 $ A_{i,j} $ 日元。
  • 然后，修建一条连接这两个车站的铁路轨道。当两个车站分别位于格子 $ (i, j) $ 和 $ (i', j') $ 时，修建轨道的费用为 $ C \times (|i - i'| + |j - j'|) $ 日元。（$ |x| $ 表示 $ x $ 的绝对值。）

高桥君的首要目标是尽可能减少修建铁路的总费用，而不是提高公民的便利性。

请输出修建铁路可能的最小总费用。

输入格式

第一行，三个整数 $ H,W,C $。

接下来 $ H $ 行 $ W $ 列，表示在各地建车站的费用 Ai,jA_{i,j}。

输出格式

共一行一个整数，表示最小花费。

输入输出样例

  • 输入#1

    3 4 2
1 7 7 9
9 6 3 7
7 8 6 4

    输出#1

    10

  • 输入#2

    3 3 1000000000
1000000 1000000 1
1000000 1000000 1000000
1 1000000 1000000

    输出#2

    1001000001

说明/提示

  • $ 2 \leq H, W \leq 1000 $
  • $ 1 \leq C \leq 10^9 $
  • $ 1 \leq A_{i,j} \leq 10^9 $
  • 输入中的所有值均为整数。

Translated by Deepseek.

输入解题思路，AI测评打分。不知道怎么写?

首页