hyhkr1374   1년 전

제일 처음에 메모리 초과가 발생하여 인접 리스트를 사용하도록 코드를 수정하였고, 또 시간 초과가 발생하여 최소 힙을 이용한 우선 순위 큐로 다익스트라 알고리즘을 진행할 수 있도록 코드를 수정하였습니다. 아래 코드가 최종 코드인데, 테스트기에 넣었을 때 반례가 발생하지 않음에도 계속 10%에서 틀렸다고 뜨네요. 메모리 초과와 시간 초과도 아닌 단순히 논리적인 부분에서 틀렸다는 건데, 아무리 봐도 어느 곳에서 틀렸는지 모르겠네요. 알려주시면 감사하겠습니다.

hyhkr1374   1년 전

저도 그런 문제에 대해 생각해봤는데, 중복된 간선이 입력되더라도 코스트에 따라 결국 비용이 최소인 간선이 사용되기 때문에 문제가 되지는 않는 것 같더라고요. 실제로 그런 중복되는 간선을 입력했을 때도 올바른 출력이 나오기도 했고요. 혹시 다른 문제는 없는 걸까요.. 

siyamaki   1년 전

다시보니깐 힙의 크기 문제였네요

E가 30만인데 힙의 크기도 2만으로 고정되어 있었습니다.

http://boj.kr/550e67c42d0245a8...

hyhkr1374   1년 전

중복된 간선이라 하더라도 어쨌든 모두 입력을 받기 때문에 힙의 크기를 간선의 개수만큼 설정해야 하는군요... 덕분에 일주일 동안 못 풀던 문제 이제서야 풀었네요. 정말 감사합니다!

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