| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 1033 | 509 | 377 | 48.458% |
재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통신망에 있는 임의의 두 서버는 통신을 할 수 있어야 한다. 두 서버가 직접 연결되어 있지 않아도 다른 서버를 통해서 통신을 할 수 있어도 된다.
서버는 행의 개수가 R개, 열의 개수가 C개인 격자로 나타낼 수 있다. 상하좌우로 인접한 서버 사이에는 직접 통신망을 설치할 수 있다. 직접 통신망을 설치하는 비용은 1, 2, 3, 4중 하나이다. 직접 통신망의 비용에는 흥미로운 성질이 하나 있는데, 한 서버 A와 인접한 B, C가 있을 때, A와 B 사이에 통신망을 설치하는 비용과 A와 C 사이에 설치하는 비용이 같은 경우는 없다는 것이다.
그림 (a)는 총 여섯 대의 서버가 있고, 각 서버 사이에 설치할 수 있는 통신망의 비용이 나와있는 그림이다. 그림 (b)는 (1, 2)와 (2, 2)에 있는 서버에서 비용이 같은 통신망이 두 개 있기 때문에, 입력으로 주어지지 않는 형태이다.
그림 (a)와 같은 그리드 네트워크의 경우 다섯 개의 통신망을 설치해서 임의의 두 서버가 통신할 수 있게 만들 수 있고, 최소 비용은 9이다. 최소가 되게 설치하는 방법은 총 두 가지가 있고, 그림 (c)와 그림 (d)에 빨간색으로 표시된 통신망을 설치하면 된다.
그리드 네트워크와 통신망의 설치 비용이 주어졌을 때, 임의의 두 서버가 통신할 수 있도록 하기 위한 최소 비용을 구해보자.
첫째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 R과 C가 공백으로 구분되어 주어진다. 다음 R개의 줄에 걸쳐서 각 줄에 C-1개의 정수가 주어지는데, 이 정수는 각 행에 놓인 C개의 서버에서 좌우로 연결하는 통신망을 설치하는 비용을 나타낸다. 다음 R-1개의 줄에 걸쳐서 각 줄에 C개의 정수가 주어지는데, 이 정수는 i번째 행과 i+1번째 행에 놓인 C개의 서버를 상하로 연결하는 통신망을 설치하는 비용을 나타낸다.
각 테스트 케이스마다 최소 비용을 한 줄에 하나씩 출력한다.
3 2 3 1 3 3 1 2 4 2 2 2 1 1 2 2 3 3 1 2 1 4 4 3 2 3 3 3 2 1
9 4 15