다익스트라 알고리즘 구현할때
priority_queue를 쓰는데
이게 기본적으로 max heap이라
min heap으로 사용하려면 저장하는 값에 음수 기호를 붙여서 넣어야하잖아
근데 난 그게 싫어서
struct cmp {
bool operator() (pair<int, int>& a, pair<int, int>& b) {
return a.second < b.second;
}
};
이거 만든다음에
priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> pq;
이런식으로 했거든
그러니까 시간이 겁나 초과되더라
이유가 뭔지 혹시 설명해줄 고수님 있으십니까
앵 에초에 원하는대로 동작하게 하려면 return a.second > b.second; 로 써야할텐데
ㄷㄷ a.second > b.second로 써야 min heap이 되나요? 저렇게 짜도 시간초과만 나고 결과는 잘나왔던거같아요
어 뭐지 > 로 하니까 시간초과 안나네요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 뭐...뭐지?
암튼 감사합니다 다시 공부해야겠네요 ㅋㅋㅋㅋ
pq가 cmp함수가 다른거랑 반대라서 maxheap으로 동작하는게 아니라 그냥 구조가 그런거라 cmp 함수를 저렇게 바꿔줘야됨
이거 이상한게 구조체 안넣고 해도 정답처리가 돼요. pq 자체가 원래 pair 넣으면 두번째 원소 기준으로 min heap이에요....?
예제가 이상한가 뭘 어떻게 해도 정답이 나오네;;
답 자체는 뭘 어떻게짜든 정답 자체는 나오게 되어있음 다만 시간복잡도 차이가 크지 maxheap쓰면 최악, minheap이 최선, 아예 비교함수를 안써버리면 첫번째 원소 기준으로 pq가 되니까 거리 기준으로는 랜덤에 가까워서 운 좋으면 뚫릴듯
아 맞네 아예 개념이 부족했네 고마워 뽀뽀쪾
꿀팁 하나 드리자면, STL 자체에 저런 비교 클래스들이 내장되어 있어서 cmp 대신 greater<>같은 식으로도 가능합니다
다익스트라가 잘못 짜도 통과되는 경우가 종종 있음 ㅇㅇ. 다익스트라는 거의 항상 답은 나오지만 시간이 얼마나 걸리냐의 문제인데 그 데이터를 정교하게 만들어야 해서.. 그래서 잘못 짠 다익스트라 통과시키지 않는 데이터 만들기 같은 글도 막 본 거 같은데
그거 근데 윗분 말대로 기본이 priority_queue, less > 인데 여기서 less 대신에 greater 넣으면 min heap으로 바뀌는 거 아닌가요?
맞음 근데 이렇게할거면 길이가 pair의 첫번째로 가야