kimeun0   2년 전


int로 하고 INF를 1000000000 (1e9)로 하거나

2087654321 로 하면 50%쯤에서 틀리고 long long으로 해야만 맞습니다.


그런데 교통비가 최대 백만이고 경로도 최대 100개인데

최대 길어봐야 int의 max인 10의 9승까지는 안가고 10의 8승이면 전체 경로합이 계산되는데

왜 long long  이 필요할까요?

경로합을 갱신할때도 from의  경로합이 아직 INF면 계산안하기 때문에 INF와 연산식이 있는것도 아닌데...

아무리 생각해도 이해가 잘 안가서 질문올려 봅니다.

knon0501   2년 전

문제를 자세히 보진 않았지만 같은 도시를 여러번 방문할 수 있기 때문이 아닐까요

namhong2001   7달 전

사이클이 있는 경우 계산값이 무척 작아질 수 있기 때문입니다. 위 코드에서 D[node]가 어느순간 무척 작은 값을 가지게 되었고 D[node] + next_cost - Money[next] 가 오버플로우를 일으켜 무척 큰값이 되는 경우를 생각해 볼 수 있습니다. 이 경우 D[next]는 더이상 업데이트 되지 않고 사이클 검출에 실패하게 됩니다.

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