kipa00   3년 전

현재 지문에 다음과 같은 말이 적혀 있습니다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자.

이런 상황은 존재할 수 없습니다. 문제 상황과 같이 이동할 수 있는 경로가 존재하는 것만으로도, 1 → 3, 1 → 4, 3 → 2, 3 → 4, 4 → 2, 4 → 3의 직접 연결된 간선이 존재한다는 것을 함의합니다. 따라서 1 3 2와 1 4 2가 제시된 경로보다 더 짧은 경로가 됩니다.

지문의 1 4 3 2를 1 4 2로, 1 3 4 2를 1 3 2로 수정해 주시면 감사하겠습니다.

댓글을 작성하려면 로그인해야 합니다.