최단경로와 쿼리
시간 제한5초메모리 제한512 MB
행이 최대 5개, 열이 100,000개인 격자에서 두 칸 사이 최소 가중치 경로를 묻는 질의에 답한다.
문제
N개의 행과 M개의 열로 이루어진 격자가 있다.
격자의 각 셀에는 가중치가 있다. i행 j열의 가중치를 Vi,j*로 표기하자.
다음과 같은 쿼리가 Q개 주어진다.
- r1 c1 r2 c2 : r1행 c1열에서 r2행 c2열로 가는 경로 중 지나는 셀의 가중치 합의 최솟값을 출력하여라.
쿼리에 대한 답을 구해보자.
단, 어떤 셀에서 한 번에 이동할 수 있는 셀은 상하좌우로 인접한 셀이다.
입력
첫 줄에 두 정수 N(1 ≤ N ≤ 5)과 M(1 ≤ M ≤ 100,000)이 주어진다.
i+1(1 ≤ i ≤ N)번째 줄에는 M개의 정수 Vi,1, Vi,2, ..., Vi,M이 주어진다. (0 ≤ Vi,j ≤ 1,000,000,000)
N+2번째 줄에 쿼리의 수를 나타내는 정수 Q(1 ≤ Q ≤ 100,000)가 주어진다.
이후 Q개의 줄에 걸쳐 쿼리를 나타내는 4개의 정수 r1, c1, r2, c2 (1 ≤ r1, r2 ≤ N, 1 ≤ c1, c2 ≤ M)가 주어진다.
출력
쿼리에 대한 답을 한 줄에 하나씩 차례로 출력하여라.