Dijkstra's single source shortest path algorithm implemented using priority queue and adjacency vector.

DijkstraPQ.cpp

#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 100'000;
using node = pair<long long, int>;
using link = pair<int, int>;

int n, m, s, mark[maxn];
long long dist[maxn];
vector<link> alist[maxn];

void dijkstra();

int main() {
  cin >> n >> m >> s;

  for (int i = 0; i < n; i++)
    dist[i] = INT_MAX;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    alist[u].push_back(make_pair(w, v));
    alist[v].push_back(make_pair(w, u));
  }
  dijkstra();
  for (int i = 0; i < n; i++)
    cout << i + 1 << ": " << dist[i] << endl;
  return 0;
}

void dijkstra() {
  priority_queue<node, vector<node>, greater<node>> pq;

  pq.push(make_pair(0, s));
  dist[s] = 0;

  while (!pq.empty()/**/) {
    node c = pq.top(); pq.pop();
    int v = c.second;
    // long long d = c.first;
    if (mark[v])
      continue;
    mark[v] = 1;
    //// we dont't see a cut-vertex twice 
    //// because of pervious if(mark[v])...
    // if (iscutv[v] && --count_cutv) 
    //   return ;
    for (size_t i = 0; i < alist[v].size(); i++) {
      int u = alist[v][i].second, w = alist[v][i].first;
      if (!mark[u] && dist[u] > dist[v] + w) {
        dist[u] = dist[v] + w;
        pq.push(make_pair(dist[u], u));
      }
    }
  }
}