shfshfdl   2년 전

우선 코드 상에서

    priority_queue <pair<int, int> > pq;
    pq.push({ start, 0 });

로 선언을 하였습니다. 그렇다면 pair는 정렬을 할때 first를 먼저 정렬하고 second를 정렬하는것으로 아는데

그렇다면 이코드는 가중치를 우선으로 소팅하는게 아니라 index를 먼저 소팅하게 되어

가중치가 크더라도 먼저 선택이 되는 경우가 발생할 것 같은데


성공으로 처리가 되네요


우선 두 쌍의 순서를 바꿔도 동일하게 정답 처리가 됩니다.


제가 모르고 있는 부분이 있는지 궁금합니다!!1


감사합니다.

kdk8361   2년 전

21번과 26번 줄에 비교구문을 넣어서 그런 듯 합니다. 다익스트라라기 보다는 bfs에 가까운 형태 같습니다.

제가 다익스트라 구현한 방식대로라면 dist비교를 하는게 아니라 -1로 초기화 한 후 -1이 아닌 경우, 즉 이미 들렀던 노드라면 continue 시켜버리기 때문에 pq pair 순서가 바뀌면 이상한 값이 들어가겠죠.

shfshfdl   2년 전

답변감사합니다.

답변 주신게 답인것 같습니다. ㅎㅎ
아직 이해가 될듯 말듯한 부분은 있으나 이부분은 최단경로 bfs로 한번
공부해보겠습니다. 약간 비슷한 느낌의 코드라 bfs에 가깝다는것도 몰랐네요

많은 도움 됬습니다. 감사합니다.

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