간선을 음수로 만들고, 벨만-포드를 시행한 다음 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로 충분히 커버 가능하다고 생각했는데.
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로 충분히 커버 가능하다고 생각했는데.
의문을 해소 시켜주실 고수분들 계실까요? 감사합니다.