kkw564   2년 전

우선순위 큐를 priority_queue<pii, vector<pii>, greater<pii>> pq; 이렇게 잡으니 시간 초과이고

priority_queue<int> pq 이렇게 잡고 -로 가중치를 주니 통과네요


많은 차이가 나는것인가요?



kkw564   2년 전

가독성을 위해 greater<int>가 좋은건가요 아니면 -로 가중치를 두는 것이 좋은건가요?

ntopia   2년 전

pair 끼리 비교할 때는

first 를 먼저 비교하고, first가 같으면 second를 비교합니다

저 위의 소스에서는 first에 정점 번호를, second에 거리를 넣고 있는데

이러면 pq.top() 의 값은  거리가 가장 짧은게 이니라 "정점번호가 가장 작은 것" 이 나오겠죠.

따라서 다익스트라 알고리즘이라고 할 수 없기 때문에 TLE가 나는 것 같네요

first랑 second를 바꿔보세요

kkw564   2년 전

바보같은 짓을 했네요 지적해주셔서 감사합니다 !

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