[DAAP] Added exercises from second exam

1 files changed, 60 insertions, 0 deletions

diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp
new file mode 100644
index 0000000..4ea0d35
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp
@@ -0,0 +1,60 @@
+#include <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+using namespace std;
+
+/*
+ * 6 <-- 11 -- 7
+ * 7 <-- 19 -- 6
+ *   -- -19 -> 6
+ *
+ */
+
+bool topo(long long c, long long& temp, vector<vector<pair<long long, long long>>>& graph, vector<long long>& mark) {
+	if (mark[c] == 2) return true;
+	if (mark[c] == 1) return false;
+	mark[c] = 1;
+	for (pair<long long, long long>& p : graph[c]) {
+		if (p.second < 0) continue;
+		bool res = topo(p.first, temp, graph, mark);
+		if (!res && temp < p.second) {
+			mark[c] = 0;
+			p.second *= -1;
+			for (pair<long long, long long>& pa : graph[p.first]) {
+				if (pa.first == c) {
+					pa.second *= -1;
+					break;
+				}
+			}
+			res = topo(p.first, temp, graph, mark);
+			if (!res) return false;
+		}
+	}
+	mark[c] = 2;
+	return true;
+}
+
+int main() {
+	ios::sync_with_stdio(false);
+	cin.tie(NULL);
+	cout.tie(NULL);
+
+	long long N, M;
+	cin >> N >> M;
+	vector<vector<pair<long long, long long>>> graph(N+1, vector<pair<long long, long long>>());
+	for (long long i = 0; i < M; i++) {
+		long long ai, bi, ci;
+		cin >> ai >> bi >> ci;
+		graph[bi].push_back({ ai, ci });
+		graph[ai].push_back({ -bi, ci });
+	}
+	for (long long t = 0; t < 20; t++) {
+		vector<long long> mark(N+1);
+		if (topo(1, t, graph, mark)) {
+			cout << t << endl;
+		}
+	}
+}