chosj1526   3년 전

주석으로 표시해둔 벨만포드함수의 바깥쪽 반복문 조건문에 의문이있습니다.

보통 다 풀이를 보면, 노드의 수만큼 +해줘서 하시더라고요(그래서 현재 문제기준으로는 N의 최대가 50이기때문에 `for(int i=1; i<=N+50; i++)`해도 맞긴해요.

근데 쓸데없는 반복을 줄이기위해 그때그때 N값에 따라 필요한만큼만 늘려보려고했습니다.

이해가 안가는건, `i<=2*(N-1)`이 안되더라고요. `i<=2*N`은 되고요.

그런데 이론적으로 N-1번 반복하는게 모든 에지를 반복하기위한 횟수이잖아요.

그럼 그 후에 또 N-1번 반복하면 결국 모든 에지를 2번 반복하는거니까, 2*(N-1)이 들어가도 가능해야하지않나요? 

확인부탁드립니다.

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