dohyeokkim   7달 전

Dijkstra에서 priority queue를 짤 때 어떤 stl container를 쓰는 것이 가장 좋을까요?

priority_queue는 nth element update가 안 돼서... googling해서 다음과 같은 답변을 참고했는데요.

http://stackoverflow.com/questions/649640/how-to-d...

그 중 조금 더 구현이 쉬워 보이는 2번째 방법이 좋을 거 같아 set을 이용했는데 TLE네요.

혹시 erase가 문제인가요?

koosaga   7달 전

find(PQ_dist.begin(), PQ_dist.end(), make_pair(dist[v], v))


이 부분은 O(N)이고 여기서 TLE입니다. find() 함수는 선형 탐색으로 구현되어 있기 때문입니다. 빠르게 원소 검색를 하려면, PQ_dist.find() 나 PQ_dist.lower_bound() 같은 거를 사용해야"만" 합니다.


그리고 개인적으로 priority_queue를 쓰는 것을 추천드립니다. std::set하고 order가 똑같고 / 일반적으로 훨씬 빠르며 / set보다 문제될 일이 적습니다. (set은 다루다 실수하면 왜 틀린지도 모르고 망하기 좋아서.. 저것도 좋은 실수의 예네요.)

ntopia   7달 전

보통 많이 쓰는 방법이 저 답변에서의 1번 방법 입니다.

dohyeokkim   7달 전

역시 그렇군요 ㅠㅠ (find를 erase라 잘못 썼네요.)

두 고수님들의 답변 감사 드립니다.

dohyeokkim   7달 전

아 그리고 koosaga님께서 말씀하신 priority_queue 이용하는 방법도 위 link에서 1번 방법을 얘기하시는 거겠죠?

dohyeokkim   7달 전

아 ㅋㅋㅋ 위와 같이 수정 했는데 또 TLE가 떠 버렸습니다...

지금 (|V| + |E|) log |V| 아닌가요??? ㅠㅠㅠ

ntopia   7달 전

priority_queue 를 그냥 쓰면

priority 가 높은것 = 값이 큰 것

부터 꺼내지게 됩니다

그래서 djikstra가 아닌 다른 요상한 짓을 하는 것으로 생각 됩니다

직접 간단한 예제를 만들어서 테스트 해보세요

ntopia   7달 전

그리고 맨 처음에는 priority_queue 에 시작점의 값만 넣어주는 것이 맞습니다

dohyeokkim   7달 전

주신 조언 다 적용해서 성공했습니다. 감사합니다.

생각해보니 거리가 무한대인 vertices를 다 넣어줄 필요가 없네요.

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