[DAAP/H2] Improved Deijkstra solution

1 files changed, 9 insertions, 8 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 0b1a994..57efbf6 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
@@ -15,8 +15,9 @@ 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> dist(N);
-	dist[s] = 0;
+	vector<long long> distlt(N, 0);
+	vector<long long> distnlt(N, 0);
+	distlt[s] = distnlt[s] = 0;
 	q.push({{ 0, s }, true});
 	while (!q.empty()) {
 		auto c = q.top().first;
@@ -25,23 +26,23 @@ long long dijkstra(long long s) {
 
 		if (lt) visitedlt[c.second] = true;
 		else    visitednlt[c.second] = true;
-		bool added = false;
 		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;
-			// cout << "From: " << c.second << " To: " << e.second << endl;
-			long long nd = dist[c.second] + e.first;
+			// 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])) {
 				dist[e.second] = nd;
 				q.push({ e, !lt });
-				added = true;
 			}
 			// cout << dist[e.second] << endl;
 		}
-		if (!added && c.second != N-1) dist[c.second] -= c.first;
 	}
-	return dist[N-1];
+	if (distlt[N-1] == 0) return distnlt[N-1];
+	if (distnlt[N-1] == 0) return distlt[N-1];
+	return min(distlt[N-1], distnlt[N-1]);
 }
 
 int main() {