[DAAP/H2] Added initial solution to homework

That times out

1 files changed, 47 insertions, 0 deletions

diff --git a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp
new file mode 100644
index 0000000..e5b9191
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp
@@ -0,0 +1,47 @@
+#include <functional>
+#include <iostream>
+#include <vector>
+#include <queue>
+using namespace std;
+
+long long N, M;
+typedef pair<long long, long long> Edge;
+
+void dfs(Edge& c, long long length, vector<vector<Edge>>& graph, bool lt, vector<bool>& visited, long long& shortest) {
+	if (c.second == N-1) {
+		shortest = min(shortest, length);
+		return;
+	}
+
+	// cout << "From: " << c.second << " " << length << endl;
+	visited[c.second] = true;
+	for (Edge& e : graph[c.second]) {
+		if (visited[e.second]) continue;
+		if ((lt && c.second < e.second) || (!lt && c.second > e.second)) {
+			dfs(e, length + e.first, graph, !lt, visited, shortest);
+		}
+	}
+	visited[c.second] = false;
+}
+
+int main() {
+	ios::sync_with_stdio(false);
+	cin.tie(NULL);
+	cout.tie(NULL);
+
+	cin >> N >> M;
+	vector<vector<pair<long long, long long>>> graph(N, vector<pair<long long, long long>>());
+	for (long long i = 0; i < M; i++) {
+		long long ai, bi, di;
+		cin >> ai >> bi >> di;
+		ai--; bi--;
+		graph[ai].push_back({ di, bi });
+		graph[bi].push_back({ di, ai });
+	}
+
+	long long shortest = 1000000005;
+	vector<bool> visited(N);
+	Edge s = {0, 0};
+	dfs(s, 0, graph, true, visited, shortest);
+	cout << shortest << endl;
+}