#K. National Railway

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

National Railway

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

题目翻译

国王想在他 H H 行 W W 列的国土上建铁路 具体地，建铁路的花费可以表示为两部分：建车站和建轨道。

  • 在 (i, j) (i,\ j) 处建车站的费用表示为 Ai,j A_{i,j}
  • 连接 (i, j) (i,\ j) 处的车站和 (i′, j′) (i',\ j') 处车站之间铁路的花费为 C × (∣i−i′∣ + ∣j−j′∣) C\ \times\ (|i-i'|\ +\ |j-j'|)

由于不修铁路会下台，而国王又没有太多钱，所以想知道在不考虑便利性的前提下修铁路的最小花费。

输入格式

第一行三个整数 H H W W C C 接下来 H H 行 W W 列表示在各地建车站的费用

输出格式

最小花费

题目描述

高橋王国は H H 行 W W 列のグリッドで表されます。北から i i 行目、西から j j 列目のマスを (i, j) (i,\ j) で表します。

このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。 鉄道建設は以下の 2 2 つのステップからなります。

  • まず、2 2 つの異なるマスを選び、それぞれに駅を建設する。マス (i, j) (i,\ j) に駅を建設すると Ai,j A_{i,j} 円の費用がかかる。
  • その後、建設した 2 2 つの駅を結ぶ線路を建設する。2 2 つの駅がマス (i, j) (i,\ j) とマス (i′, j′) (i',\ j') にあるとき、これらを結ぶ線路の建設をすると C × (∣i−i′∣ + ∣j−j′∣) C\ \times\ (|i-i'|\ +\ |j-j'|) 円の費用がかかる。（ここで、∣x∣ |x| は x x の絶対値を表す。）

高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています。 鉄道建設にかかる費用として考えられる最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

H H W W C C A1,1 A_{1,1} A1,2 A_{1,2} ⋯ \cdots A1,W A_{1,W} ⋮ \vdots AH,1 A_{H,1} AH,2 A_{H,2} ⋯ \cdots AH,W A_{H,W}

输出格式

鉄道建設にかかる費用として考えられる最小値を出力せよ。

样例 #1

样例输入 #1

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

样例输出 #1

10

样例 #2

样例输入 #2

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

样例输出 #2

1001000001

提示

制約

  • 2 ≤ H, W ≤ 1000 2\ \leq\ H,\ W\ \leq\ 1000
  • 1 ≤ C ≤ 109 1\ \leq\ C\ \leq\ 10^9
  • 1 ≤ Aij ≤ 109 1\ \leq\ A_{ij}\ \leq\ 10^9
  • 入力はすべて整数

Sample Explanation 1

マス (1, 1) (1,\ 1) とマス (2, 3) (2,\ 3) に駅を建設すると、駅の建設費用が 1 + 3 = 4 1\ +\ 3\ =\ 4 円、 線路の建設費用が 2 × (∣1−2∣ + ∣1−3∣) = 6 2\ \times\ (|1-2|\ +\ |1-3|)\ =\ 6 円となり、鉄道建設にかかる費用は 4+6 = 10 4+6\ =\ 10 円となります。 これが費用として考えられる最小値です。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 37ms
  • Powered by Hydro v4.9.27 Community