[DAAP/H2] Completely solved homework1

100/100 points

1 files changed, 20 insertions, 18 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
index 57efbf6..1e007d8 100644
--- 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
@@ -7,33 +7,35 @@ using namespace std;
 long long N, M;
 
 typedef pair<long long, long long> Edge;
+// Performance improvement - Static array and different neighbour vectors for bigger and smaller
 pair<vector<Edge>, vector<Edge>> graph[100005] = { { vector<Edge>(), vector<Edge>() } };
-bool visited[100005] = { false };
 
-typedef pair<Edge, bool> Qedge;
+// Performance improvement? - Edge& rather than Edge
+typedef pair<Edge&, bool> Qedge;
+
 long long dijkstra(long long s) {
-	priority_queue<Qedge, vector<Qedge>, greater<Qedge>> q;
-	vector<bool> visitedlt(N, false);
-	vector<bool> visitednlt(N, false);
-	vector<long long> distlt(N, 0);
-	vector<long long> distnlt(N, 0);
+	// Performance improvement - queue rather than priority_queue
+	queue<Qedge> q;
+	// Wrong answer on multiple tests - remove visited logic
+
+	// Performance improvement - from vector to statis array
+	// Wrong answer on a couple of tests - not init with { 0 }
+	long long distlt[100005] = { 0 };
+	long long distnlt[100005] = { 0 };
 	distlt[s] = distnlt[s] = 0;
-	q.push({{ 0, s }, true});
+	Edge b = { 0, s };
+	q.push({b, true});
 	while (!q.empty()) {
-		auto c = q.top().first;
-		bool lt = q.top().second;
+		auto c = q.front().first;
+		bool lt = q.front().second;
 		q.pop();
 
-		if (lt) visitedlt[c.second] = true;
-		else    visitednlt[c.second] = true;
 		for (Edge& e : (lt) ? graph[c.second].second : graph[c.second].first) {
-			if (e.second == 0 || e.second== c.second ||
-				(!lt && visitedlt[e.second]) ||
-				(lt && visitednlt[e.second])) continue;
+			if (e.second == 0 || e.second == c.second) continue;
 			// cout << "From: " << c.second+1 << " To: " << e.second+1 << endl;
-			vector<long long>& dist = (lt) ? distlt : distnlt, distc = (!lt) ? distlt : distnlt;
-			long long nd = distc[c.second] + e.first;
-			if ((dist[e.second] == 0 || nd < dist[e.second])) {
+			long long (&dist)[100005] = (lt) ? distlt : distnlt;
+			long long nd = ((!lt) ? distlt[c.second] : distnlt[c.second]) + e.first;
+			if (dist[e.second] == 0 || nd < dist[e.second]) {
 				dist[e.second] = nd;
 				q.push({ e, !lt });
 			}