ognboss1   1년 전

다익스트라큐에서 우선순위 큐를 사용하여 거리의 갱신을 시도하는데

이때 우선순위큐안에서의 문제점이 거리가 갱신될때마다 푸쉬를 해주면 그것또한 메모리 낭비일거 같은데

만약 

priority queue <pair <int, int>> Q;
가 있다고 가정하고 first가 vertex i이고 second가 dist[i]라고 합니다.

그러면 start vertex에서 한번 거리의 갱신이 이루어 지면 그것이 주소값처럼 변경된 dist[i]가 Q값안에 바뀌게끔은 설정할 수가 없는건가요?

계속 푸쉬해주고 질문에서 봤던 해답들 처럼 그 dist[i]가 현재의 dist[i]보다 크다면 continue하는 방식말고 저렇게 바뀐값이 Q안에 값에도 영향을 줄수 없을가요?

한마디로 Q안에 주소값들을 주고 우선순위를 결정할때 그 주소값들을 참조해서 pop을 하게끔 할수는 없을까요?


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