summaryrefslogtreecommitdiff
path: root/Year_2
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2023-01-19 22:22:44 +0100
committerSanto Cariotti <santo@dcariotti.me>2023-01-19 22:22:44 +0100
commitf5276526eb7f5ad1d3a97dc555977d0196b4c796 (patch)
treee79e99df54606a42bc4cb9197f81efc72154983e /Year_2
parent18c47b311522f0421e6cd479ff174093df1516e7 (diff)
add bellmanford-p
Diffstat (limited to 'Year_2')
-rw-r--r--Year_2/Algorithms/bellman-ford-p.cc110
1 files changed, 110 insertions, 0 deletions
diff --git a/Year_2/Algorithms/bellman-ford-p.cc b/Year_2/Algorithms/bellman-ford-p.cc
new file mode 100644
index 0000000..27668f5
--- /dev/null
+++ b/Year_2/Algorithms/bellman-ford-p.cc
@@ -0,0 +1,110 @@
+#include <iostream>
+#include <fstream>
+#include <map>
+#include <vector>
+#define INF 9999999
+
+using namespace std;
+
+typedef pair<int, int> pii;
+typedef tuple<int, int, int> tii;
+
+class Graph
+{
+public:
+ explicit Graph(size_t size, size_t k)
+ : sizes_ { size }
+ , k_ { k }
+ {
+ for (size_t i = 0; i < size; ++i)
+ add_node(i);
+ }
+
+ Graph*
+ add_node(int x)
+ {
+ auto it = nodes_.find(x);
+
+ if (it != nodes_.end()) {
+ nodes_[x] = vector<pii>();
+ }
+
+ return this;
+ }
+
+ Graph*
+ add_edge(int x, int y, int w)
+ {
+ nodes_[x].push_back({y, w});
+ edges_.push_back({x, y, w});
+
+ return this;
+ }
+
+ void
+ bellmanford(int s, int r, ostream& out)
+ {
+ vector<int> dist(sizes_, INF);
+ dist[s] = 0;
+
+ for (size_t i = 0; i < min(k_, sizes_); ++i) {
+ for (const auto& e : edges_) {
+ auto u = get<0>(e);
+ auto v = get<1>(e);
+ auto w = get<2>(e);
+
+ if (dist[u] != INF && dist[v] > dist[u] + w) {
+ dist[v] = dist[u] + w;
+ }
+ }
+ }
+
+ if (dist[r] == INF) {
+ out << "inf." << endl;
+ } else {
+ out << dist[r] << endl;
+ }
+ }
+
+private:
+ map<int, vector<pii>> nodes_;
+ vector<tii> edges_;
+ size_t sizes_;
+ size_t k_;
+};
+
+int
+main(int argc, char** argv)
+{
+ int nt = (argc > 1) ? stoi(argv[1]) : 100;
+ int n, m, k, s, r;
+ string ch;
+ int n1, n2, w;
+
+ ifstream fin("input.txt");
+ ofstream fout("output.txt");
+
+ for (int i = 0; i < nt; ++i) {
+ fin >> n >> m >> k;
+
+ Graph* g = new Graph(n, k);
+
+ for (int j = 0; j < m; ++j) {
+ fin >> ch;
+ n1 = stoi(ch.substr(1, ch.length()));
+ fin >> n2 >> ch;
+ w = stoi(ch.substr(0, ch.length()-1));
+
+ g->add_edge(n1, n2, w);
+ }
+
+ fin >> s >> r;
+ g->bellmanford(s, r, fout);
+
+ delete g;
+ }
+
+ fout.close();
+ fin.close();
+ return 0;
+}