shwjdgh3842   2년 전

종만북을 참조해서 거의 그대로 구현한 코드인데 어떤 반례가 있는지 모르겠습니다.

(댓글에 수정코드와 틀린 부분 추가했습니다)

shwjdgh3842   2년 전

31~33번째 줄 코드를 추가했더니 맞았다고 하네요

그런데 수정 이전코드에서는 시작점과 동떨어진 음수사이클이 있다고 가정하더라도 충분히 큰 수를 빼주었기 때문에 도달하지 못하는 점들에 대해 재대로 탐색할 수 있지 않나요??

수정 이전코드가 왜 틀렸는지 잘 이해가 안되네요..

nsg   2년 전

첫번째 코드 이렇게 수정하니 통과했어요.

시작점과 동떨어진 음수사이클이 있어도 마지막 완화할 때 그 음수 사이클에 의해 완화에 성공합니다.

그리고 ispossible이 false가 되죠.

그 곳은 애초에 방문할 수 없었던 곳이니 카운트 안하는게 맞는거 같아요.


그리고 플로우 방지로

 const long long inf = INT64_MAX/2;

를 수정했습니다.

주어진 입력을 무식하게 계산하면 INF에서 음수와 완화되면 INF -6,000*500*10,000 = INF -300억이되기 때문입니다.


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