about summary refs log tree commit diff
path: root/12
diff options
context:
space:
mode:
authorNguyễn Gia Phong <vn.mcsinyx@gmail.com>2018-03-28 22:46:21 +0700
committerNguyễn Gia Phong <vn.mcsinyx@gmail.com>2018-03-28 22:46:21 +0700
commite6b3d79abf4135983e40b4c5270d6e29427dd2bc (patch)
tree4136347edeed030b244419b362f2d1e50e0a4e0a /12
parent4bc82188482e63ec52acb71985039d3d33378a7a (diff)
downloadcp-e6b3d79abf4135983e40b4c5270d6e29427dd2bc.tar.gz
Add 12/TP-HN-2009/R2/BAI2.CPP
Diffstat (limited to '12')
-rw-r--r--12/TP-HN-2009/R2/BAI2.CPP58
1 files changed, 58 insertions, 0 deletions
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;
+}