hyhkr1374   1년 전

해당 문제에 대해 우선 순위 큐를 사용하지 않고 다익스트라 알고리즘만을 사용한 코드를 짰습니다. 테스트기에 돌려본 결과 N=20000일 때 런타임 에러가 발생하여, 2차원 그래프 배열과 visited, dist 배열을 모두 malloc으로 동적할당했음에도 계속 N=20000일 때 런타임 에러가 발생한다고 뜨네요. 이 문제는 우선 순위 큐를 사용해야만 풀 수 있는 건가요?

not_strober   1년 전

이 문제의 메모리 제한은 256MB인데 graph 하나에서만 (V + 1) * (V + 1)개로 4억 개의 행렬 원소를 할당하려고 시도하고 있습니다. 인접 리스트 + 우선순위 큐를 사용하는 것을 의도하고 만들어진 문제로 보입니다.

hyhkr1374   1년 전

넵 감사합니다. 우선 순위 큐를 사용해봐야겠네요.

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