From e6b3d79abf4135983e40b4c5270d6e29427dd2bc Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Wed, 28 Mar 2018 22:46:21 +0700
Subject: Add 12/TP-HN-2009/R2/BAI2.CPP

---
 12/TP-HN-2009/R2/BAI2.CPP | 58 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
 create mode 100644 12/TP-HN-2009/R2/BAI2.CPP

diff --git a/12/TP-HN-2009/R2/BAI2.CPP b/12/TP-HN-2009/R2/BAI2.CPP
new file mode 100644
index 0000000..a47760f
--- /dev/null
+++ b/12/TP-HN-2009/R2/BAI2.CPP
@@ -0,0 +1,58 @@
+#include <iostream>
+#include <fstream>
+#include <functional>
+#include <map>
+#include <queue>
+#include <vector>
+
+#define ENC(distance, current, coupon) (((distance) << 14) + ((current) << 1) + coupon)
+#define DEC_D(data) ((data) >> 14)
+#define DEC_C(data) ((data) >> 1 & 0b1111111111111)
+#define DEC_B(data) ((data) & 1)
+
+using namespace std;
+
+int
+main()
+{
+  ifstream infile;
+  infile.open("BAI2.INP");
+  int n, m;
+  infile >> n >> m;
+  map<long long, map<long long, long long>> c;
+  long long k, i, j, l;
+  for (k = 0; k < m; k++)
+    {
+      infile >> i >> j >> l;
+      c[i][j] = l;
+    }
+  infile.close();
+
+  priority_queue<long long, vector<long long>, greater<long long>> q;
+  for (auto& item : c[1])
+    {
+      q.push(ENC(item.second, item.first, 1));
+      q.push(ENC(0, item.first, 0));
+    }
+
+  long long tmp;
+  while (!q.empty())
+    {
+      tmp = q.top();
+      q.pop();
+      if (DEC_C(tmp) == n)
+        break;
+      for (auto& item : c[DEC_C(tmp)])
+        q.push(ENC(DEC_D(tmp) + item.second, item.first, DEC_B(tmp)));
+      if (DEC_B(tmp))
+        for (auto& item : c[DEC_C(tmp)])
+          q.push(ENC(DEC_D(tmp), item.first, 0));
+    }
+
+  ofstream outfile;
+  outfile.open("BAI2.OUT");
+  outfile << DEC_D(tmp) << endl;
+  outfile.close();
+
+  return 0;
+}
-- 
cgit 1.4.1