망한 문제입니다.

공식 풀이는 시작점과 끝점에서 동시에 BFS를 돌리는 테크닉(bidirectional BFS)과 A* 알고리즘을 소개하고 있는데, 둘 다 충분히 효율적이지 않습니다.
모범 코드는 그리디한 전략으로 답의 상한을 정한 뒤 A* 알고리즘과 유사한 탐색을 적용하고 있는데 그리디의 구현과 거리 함수가 모두 엉망이기 때문에 아주 작은 범위에서도 쉽게 반례를 찾을 수 있습니다.