sk251525   4년 전

O(N^2) Prim을 하고나서 O(N*log N)을 해봤는데 이 문제의 데이터가 빈약함을 알고있음에도 첫데이터부터 광탈하는것같습니다.

무엇이 문제인지 알려주신다면 감사하겠습니다.

djm03178   4년 전

각 정점에 대한 최소 가중치가 갱신될 때마다 그 정점이 다시 우선순위 큐에 들어가게 되므로, 결과적으로 정점의 수보다 많은 횟수를 우선순위 큐에서 빼게 됩니다.

sk251525   4년 전

감사합니다!! visit배열을 생성해서 해결했습니다. 

또 테스트케이스가 약해서 통과한거지 dist배열 초기값을 0이아닌 1로 했더군요..ㅠ 엄청난 실순데.. 

늘 답변에 감사드립니다.

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