From a3dd2581ed4847670f81157091016c14ca18803d Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Tue, 14 Jan 2020 18:29:11 +0700
Subject: [usth/MATH2.3] Mathemate Discretely

---
 usth/MATH2.3/2/dijkstra.cc | 55 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
 create mode 100644 usth/MATH2.3/2/dijkstra.cc

(limited to 'usth/MATH2.3/2/dijkstra.cc')

diff --git a/usth/MATH2.3/2/dijkstra.cc b/usth/MATH2.3/2/dijkstra.cc
new file mode 100644
index 0000000..e8a7931
--- /dev/null
+++ b/usth/MATH2.3/2/dijkstra.cc
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <deque>
+#include <queue>
+#include <unordered_map>
+#include <vector>
+
+#define ENCODE(w, c, p) (((w) << 20) + ((c) << 10) + (p))
+#define WEIGHT(x) ((x) >> 20)
+#define CUR(x) ((x) >> 10 & 1023)
+#define PREV(x) ((x) & 1023)
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n, a, b, w, s, e;
+  unordered_map<size_t, unordered_map<size_t, size_t>> edges;
+
+  cin >> n >> s >> e;
+  for (size_t i = 0; i < n; ++i)
+    {
+      cin >> a >> b >> w;
+      edges[a][b] = edges[b][a] = w;
+    }
+
+  unordered_map<size_t, size_t> prev;
+  priority_queue<size_t, vector<size_t>, greater<size_t>> pq;
+  pq.push (ENCODE (0, s, s));
+
+  while (!pq.empty ())
+    {
+      size_t p = pq.top ();
+      a = PREV (p);
+      b = CUR (p);
+      w = WEIGHT (p);
+      if (!prev[b])
+        prev[b] = a;
+      if (b == e)
+        break;
+      pq.pop ();
+
+      for (auto const& [i, v] : edges[b])
+        if (!prev[i])
+          pq.push (ENCODE (w + v, i, b));
+    }
+
+  deque<size_t> d;
+  for (; e != s; e = prev[e])
+    d.push_front (e);
+  d.push_front (e);
+  for (auto const& i : d)
+    cout << i << " ";
+  cout << "(length of " << w << ")" << endl;
+}
-- 
cgit 1.4.1