kkwandy   1년 전

아래 제가 제출한 코드입니다.

간선을 음수로 만들고, 벨만-포드를 시행한 다음 1번 더 iterate하여 distance 배열 값이 바뀌는(=사이클이 생기는) 부분에서 end city에 도달할 수 있나/없나로 문제 풀었습니다.
아래 제 코드에서 distance 배열을 int로 하면 WA, long으로 하면 맞았습니다 가 뜨던데 왜 그런가요?

문제 조건에서 오버플로가 일어나지 않는다고 판단했습니다(가중치 최대 10^6, M=50, distance 배열체크 -> 50 * (10^6) * 2(=마지막 1회 iterate시 cycle 때문에 전체 2배) = 10^8). 이 되어 int로 충분히 커버 가능하다고 생각했는데.

의문을 해소 시켜주실 고수분들 계실까요? 감사합니다.

jbw9964   1년 전

`distance.length` 번 `distance` 배열을 업데이트 하므로 N 을 한번 곱해야 합니다.

도시가 하나의 거대한 음수 사이클을 이룬 경우를 생각하면 편할 것 같습니다.

50 * 50 * 1,000,000 = 2.5 * 10^9 이고 2^31 ~= 2.14 * 10^9 이므로 아슬아슬하게 int 범위가 넘어가네요.

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