From 26cd07b4d31e09b8b5bacb1c4d1664d93313ca2e Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Wed, 18 Jan 2023 23:26:18 +0100 Subject: add dijkstra --- Year_2/Algorithms/dijkstra.cc | 175 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 175 insertions(+) create mode 100644 Year_2/Algorithms/dijkstra.cc (limited to 'Year_2') diff --git a/Year_2/Algorithms/dijkstra.cc b/Year_2/Algorithms/dijkstra.cc new file mode 100644 index 0000000..9392e20 --- /dev/null +++ b/Year_2/Algorithms/dijkstra.cc @@ -0,0 +1,175 @@ +#include +#include +#include +#include +#include +#define INF 999999 + +using namespace std; + +template +class Graph { +public: + Graph() + { + } + + ~Graph() + { + } + + Graph* + add_node(K x) + { + auto it = nodes_.find(x); + + if (it == nodes_.end()) { + nodes_.insert({ x, vector>() }); + size_++; + } + + return this; + } + + Graph* + add_edge(K x, K y, H w) + { + auto u = nodes_.find(x); + auto v = nodes_.find(y); + + if (u != nodes_.end() && v != nodes_.end()) { + nodes_[x].push_back({ y, w }); + } + + return this; + } + + size_t + dijkstra(K s, K r) + { + typedef pair phk; + priority_queue, greater> pq; + + auto i = nodes_.find(s); + auto j = nodes_.find(r); + + if (i == nodes_.end() || j == nodes_.end()) { + return INF; + } + + map dist; + + pq.push({ 0, s }); + + for (const auto& it : nodes_) + dist.insert({ it.first, INF }); + + dist[s] = 0; + + while (!pq.empty()) { + int u = pq.top().second; + pq.pop(); + + for (auto const& i : nodes_[u]) { + int v = i.first; + int w = i.second; + + if (dist[v] > dist[u] + w) { + dist[v] = dist[u] + w; + pq.push({ dist[v], v }); + } + } + } + + return dist[r]; + } + +private: + size_t size_ { 0 }; + map>> nodes_; +}; + +int +main(int argc, char** argv) +{ + int tasks = (argc > 1) ? stoi(argv[1]) : 100; + int n, m; + string buf; + + ifstream fin("input.txt"); + ofstream fout("output.txt"); + + for (int i = 0; i < tasks; ++i) { + string t; + + fin >> n >> m >> t; + + Graph* g = new Graph(); + if (t == "int") { + int k; + + for (int j = 0; j < n; ++j) { + fin >> k; + g->add_node(k); + } + + int n1, n2, w; + + for (int j = 0; j < m; ++j) { + fin >> buf; + n1 = stoi(buf.substr(1, buf.length())); + fin >> buf; + n2 = stoi(buf); + fin >> buf; + w = stoi(buf.substr(0, buf.length() - 1)); + + g->add_edge(n1, n2, w); + } + int s, r; + fin >> s >> r; + + auto dist = g->dijkstra(s, r); + if (dist == INF) + fout << "inf." << endl; + else + fout << dist << endl; + + } else { + double k; + + for (int j = 0; j < n; ++j) { + fin >> k; + g->add_node(k * 10); + } + + double n1, n2; + int w; + + for (int j = 0; j < m; ++j) { + fin >> buf; + n1 = stod(buf.substr(1, buf.length())); + fin >> buf; + n2 = stod(buf); + fin >> buf; + w = stoi(buf.substr(0, buf.length() - 1)); + + g->add_edge(n1 * 10, n2 * 10, w); + } + + double s, r; + fin >> s >> r; + + auto dist = g->dijkstra(s * 10, r * 10); + if (dist == INF) + fout << "inf." << endl; + else + fout << dist << endl; + } + delete g; + } + + fin.close(); + fout.close(); + + return 0; +} -- cgit v1.2.3-18-g5258