성준이는 연구실 추계 워크샵으로 산간 지역에 가게 되었다. 워크샵에서 교수님은 연구실 학생들에게 각각 산봉우리에 오르게 한 다음에, 각자 알아서 가장 가까운 산장으로 들어가라고 지시했다.
봉우리 중에 일부는 산장이 설치되어있고, 봉우리 사이에는 등산로가 개설되어 있다. 그리고 봉우리에는 고유 번호가 붙어있다.
등산로 노선망은 아래와 같은 조건으로 개설되어 있다.
-
임의의 두 봉우리는 단방향 등산로로 연결된다.
-
임의의 두 봉우리 사이에 등산로가 하나도 없을 수도 있고, 여러 등산로가 존재할 수도 있다.
-
임의의 봉우리에서 산장이 설치된 산 봉우리로 갈 수 있는 경로가 최소한 하나 이상 존재한다.
임의의 산 봉우리 A에서 B까지의 “거리”는 등산로 노선망에서 A에서 출발해서 B로 갈 수 있는 최단 경로의 길이로 결정된다.
가장 늦게 산장에 들어온 학생에게는 한 학기 내로 논문 한 편을 써야 하는 벌칙이 주어질 수 있다. 그래서 성준이는 산장으로부터 가장 먼 봉우리를 피하고 싶다. 성준이를 위해 산장까지의 거리가 가장 먼 봉우리와 그 봉우리로부터 산장까지의 거리를 구해서 알려주자.
(문제가 잘 이해되지 않는 경우 아래의 도움말을 읽어주세요)