na982   2년 전

벨만 포드에서  목적지에 연결되는 음수 사이클을 처리 하기 위해서 2 * n 만큼 반복하면서

반복문이 n - 1 이후에 목적지가 갱신되는 경우를 체크 했습니다.

if ((i >= (n - 1)) && (there == e)) {
negative_cycle = 1;
break;
}

그리고 나머지는 전형적인 벨만 포드 알고리즘을 구현했는데요; 어느 부분이 틀렸는지 잘 모르겠네요;;

고수님들 도움 부탁 드립니다.


na982   2년 전

negative_cycle 을 따로 queue를 이용해서 탐색하면; ac가 뜨네요;

하지만 위의 코드 처럼 2 * n 만큼 반복해서 돌면; 처리가 될꺼라 생각했는데; 안되네요; 반례를 모르겠어요~

고수님들 답변좀 부탁 드립니다.

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