Dijkstra with array instead of unordered_map

dijskstra_pq.cpp

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int LIMIT = 1e5;

struct Node{
  int id;
  int co;
  bool ck;
};

class Compare {
  public:
    bool operator() (Node* a, Node* b){
      return a->co > b->co;
    }
};

void ___showedge(int** edges,int nodenum){
  for(int i = 0; i < nodenum; ++i){
    for(int j = 0; j < nodenum; ++j){
      if(edges[i][j] == LIMIT) cout << "INF" << " ";
      else cout << setw(3) << edges[i][j] << " "; 
    }
    cout << endl;
  }
  cout << endl;
}

void ___shownodes(Node* nodes, int nodenum){
  for(int i = 0; i < nodenum; ++i)
    cout << nodes[i].id << ":" << nodes[i].co << " " << nodes[i].ck << endl;
  cout << endl;
}

void showpath(int* path, int nodenum, Node* nodes){
  vector<int> rev;
  int node = nodenum-1;
  while(true){
     rev.push_back(node);
     node = path[node];
     if(node==0) break;
  }
  rev.push_back(0);
  reverse(rev.begin(),rev.end());
  for(auto &p: rev)
     cout << p << "(" << nodes[p].co << ") -> ";
  cout << "GOAL!!" << endl;
}

void dijkstra(int** edges,int nodenum){
  Node* nodes = new Node[nodenum];
  for(int i = 0; i < nodenum; ++i){
    nodes[i].id = i;
    nodes[i].co = LIMIT;
    nodes[i].ck = false;
  }

  priority_queue<Node*,vector<Node*>,Compare> pq;
  nodes[0].co = 0;
  pq.push(&nodes[0]);

  Node* node;
  int* path = new int[nodenum];
  while(0<pq.size()){
    //___shownodes(nodes,nodenum);
    node = pq.top(); pq.pop();
    node->ck = true;
    if(node->id == nodenum-1) break;
    for(int i = 0; i < nodenum; ++i){
      if(nodes[i].ck) continue;
      if(edges[node->id][i] == LIMIT) continue;
      if(node->co+edges[node->id][i] < nodes[i].co){
        nodes[i].co = node->co+edges[node->id][i];
        path[i] = node->id;
        pq.push(&nodes[i]);
      }
    }
  }
  //___shownodes(nodes,nodenum);
  showpath(path,nodenum,nodes);
}

int main(){
  int nodenum;
  int nodenum1;
  int edgenum=0;
  cout << "# of nodes: ";
  cin >> nodenum;
  cout << "# of edges: ";
  while(edgenum < nodenum-1 || nodenum*nodenum < edgenum)
    cin >> edgenum;
  cout << endl;

  int** edges = new int*[nodenum];
  for(int i = 0; i < nodenum; ++i)
    edges[i] = new int[nodenum];

  for(int i = 0; i < nodenum; ++i){
    for(int j = 0; j < nodenum; ++j)
      edges[i][j]=LIMIT;
  }

  for(int i = 0; i < nodenum-1; ++i)
    edges[i][i+1]=1000-1;

  int fr,to,co;
  for(int i=0;i<edgenum-(nodenum-1);i++){
    while(true){
      fr=rand()%nodenum;
      to=rand()%nodenum;
      co=rand()%1000;
      if(edges[fr][to] == LIMIT){
        edges[fr][to]=co;
        break;
      }
    }
  }
  //___showedge(edges,nodenum);

  dijkstra(edges,nodenum);

  return 0;
}

$ time ./dijkstra_pq
# of nodes: 1000
# of edges: 5000

0(0) -> 957(260) -> 95(481) -> 72(647) -> 149(839) -> 937(1460) -> 55(1951) -> 999(2208) -> GOAL!!
./dijkstra_pq  0.01s user 0.00s system 0% cpu 4.411 total

$ time ./dijkstra_pq
# of nodes: 100000
# of edges: 500000

zsh: killed     ./dijkstra_pq
./dijkstra_pq  11.99s user 6.09s system 80% cpu 22.371 total