최단경로와 쿼리

풀이

격자의 크기가 작다면 다익스트라나 DP로 간단히 풀 수 있겠지만, $M$이 10만으로 해당 방법을 그대로 적용할 수가 없다.

적당히 머릿속으로 경로를 그려보면서 알 수 있는 사실은, $c1$에서 $c2$로 가려면 그 사이에 있는 열들을 반드시 지나야 한다는 것이다. 즉, 사이에 있는 열을 $m$이라고 하면, $m$의 왼쪽에 있는 열과 오른쪽에 있는 열 간에 이동하려면 반드시 $m$을 지나야 한다.

왼쪽, 오른쪽, 중간... 단어만 들어도 굉장히 분할정복이 잘 될 것 같지 않은가? 그 생각대로, $m$번째 열의 각 행을 시작점으로 해서 각각 다익스트라를 돌려서 $m$을 지날 때 범위 내의 쿼리들의 답을 업데이트해 줌으로써 문제를 풀 수 있다!

구현을 할 때는 약간 신경써줘야 할 부분이 있을 수도 있다.