우선 순위 큐 소스 코드

이전까지 내용에서는 priority_queue<int> pq로 두어 음의 가중치로 push 함으로써 우선순위 큐를 표현했지만

아래 코드는 greater<>을 써서 최소 힙을 구현하여 음의 가중치 없이 바로 이용할 수 있다.

하지만 프로그래밍을 하고 돌려본 결과 확실히 여러 함수들을 이용하여 우선순위 큐를 작동시키니

시간이 음의 가중치를 이용하는 것 보다 훨씬 많이 들었다.

이 코드의 장점 :: 음의 가중치가 없기에 헷갈리지 않고 가독성이 좋다.

이 코드의 단점 :: 음의 가중치를 이용한 pq보다 느리다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <iostream> #include <cstdio> #include <functional> #include <queue> #include <limits.h> #include <vector>   using namespace std;   vector<int> dijkstra(int src, int V, int E) {     // 정점 개수만큼 INT_MAX로 초기화     vector<int> dist(V, INT_MAX);     dist[src] = 0; // 자기 자신 최단거리는 0       priority_queue<pii, vector<pii>, greater<pii>> pq;       pq.push(pii(src, 0));       while (!pq.empty())     {         // cost :: 현재 정점까지 최단 거리         int here = pq.top().first;         int cost = pq.top().second;           pq.pop();           // dist :: 현재 정점이 가지고 있던 최단 거리         // 현재 정점이 가지고 있던 최단 거리가          if (dist[here] < cost)             continue;           for (int i = 0; i < adj[here].size(); i++)         {             int there = adj[here][i].first;             // thereDist :: 현재 정점에서 가중치를 더한 거리             int thereDist = adj[here][i].second + cost;               // 현재 정점이 가지고 있던 최단거리가 현재 정점에서 가중치를 더한 거리보다 크면 바꾼다.             if (dist[there] > thereDist)             {                 dist[there] = thereDist;                 pq.push(pii(there, thereDist));             }         }     }       return dist; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus