5회 문제풀이 10 / ABC 210 D - National Railway

ABC 210 D - National Railway

【문제 개요】

타카하시왕국은 H행 W열의 칸으로 표시됩니다. 북쪽으로부터 i행째, 서쪽에서부터 j열째의 칸은 (i, j)로 표시됩니다.(1 ≤ i ≤ H, 1 ≤ j ≤ W)
이번에 타카하시 왕국의 국민으로부터 교통의 편리성을 위해 철도의 건설을 요구하는 목소리가 다수 전해졌고, 국왕의 타카하시군은 철도를 건설해야 합니다.
철도 건설은 다음과 같이 2단계로 구성됩니다.

• 먼저, 2개의 같지않은 칸을 고르고, 각각에 역을 건설합니다. (i, j)칸에 역을 건설하면 Aᵢⱼ원의 비용이 소모됩니다.
• 그 후, 건설한 두개의 역을 연결하는 선로를 건설합니다. 2개의 역이 (i, j)칸과 (i’, j’)칸에 있을 경우, 이 둘을 연결하는 선로의 비용은 C ✖ (|i - i’| + |j - j’|)원입니다.(여기서 |x|는 x의 절대값을 의미합니다.) 타카하시군은 국민의 편리성을 높히는 것보다 철도 건설에 드는 비용을 적게 억제하는것을 우선하고 싶습니다.
  철도 건설에 드는 비용의 최소값을 출력하시오.

힌트 : 동적 프로그래밍(DP)
최소값 갱신 기법
맨해튼 거리의 특성

【전제】

• 2 ≤ H, W ≤ 1000
• 1 ≤ C ≤ 10⁹
• 1 ≤ Aᵢⱼ ≤ 10⁹
• 입력은 모두 정수이다.

【입력 형태】

H W C
A₁₁ A₁₂ ... A₁w
... 
Aₕ₁ Aₕ₂ ... Aₕw

【출력 형태】

철도 건설에 드는 비용으로 생각할 수 있는 최솟값을 출력하라.

【예시】

입력 예 1

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

출력 예 1

10

(1, 1)칸과 (2, 3)칸에 역을 건설하면 역의 건설비용은 1 + 3 = 4원이며 선로의 건설 비용은 2 x (|1 - 2| + |1 - 3|) = 6원이므로 총 비용은 4 + 6 = 10원이다. 이것이 최소 금액이다.

입력 예 2

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

출력 예 2

1001000001

출처 : https://atcoder.jp/contests/abc210/tasks/abc210_d