akswnd98   3년 전

아래의 소스코드로 AC판정을 받았습니다.

아래의 소스코드는 "모든 지점"들이 "시작 지점"인 "지점 1"로 가는 경로가 존재할 때 정상적으로 AC판정을 받을 수 있습니다.

가령 "지점 1"에서 "다른 지점"으로 가는 웜홀은 존재하지만 "다른 지점"에서 "지점 1"로 가는 웜홀이 없고 "지점 1"과 "다른 지점"을 연결하는 어떠한 도로도 없을 때의 경우를 다룬 "TEST CASE"는 AC판정을 받을 수 없습니다.

TEST CASE를 하나 예로 들어보겠습니다.

만약

1

5 1 4

1 2 1

1 3 0

3 4 1

4 5 1

5 3 1

과 같은 입력을 주었다면 정상적인 출력은 NO입니다. 하지만 위의 소스코드는 "지점 1"에서 시작하는 벨만-포드 알고리즘으로 단순히 음의 사이클을 발견했기 때문에 YES를 출력합니다.

즉 문제에  "모든 지점"들이 "시작 지점"인 "지점 1"로 가는 경로가 존재한다라는 조건을 추가하거나, 위의 예시와 같은 TEST CASE를 판정 머신에 추가하는 것이 좋을 것 같습니다.

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