경찰차
Problem
https://www.acmicpc.net/problem/2618
Summary
이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 있다. 경찰 본부에서는 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려 주고, 연락 받은 경찰차는 그 위치로 가장 빠른 길을 통해 이동하여 사건을 처리한다. (하나의 사건은 한 대의 경찰차가 처리한다.)
도로의 개수 N(5≤N≤1,000), 사건의 개수 W(1≤W≤1,000)
Idea
전체 탐색으로는 2^40으로 ac를 받을 수 없다