[DAAp/H2] Reworked solution to use Deijkstra, got half points

1 files changed, 43 insertions, 20 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 e5b9191..0b1a994 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
@@ -5,23 +5,43 @@
 using namespace std;
 
 long long N, M;
+
 typedef pair<long long, long long> Edge;
+pair<vector<Edge>, vector<Edge>> graph[100005] = { { vector<Edge>(), vector<Edge>() } };
+bool visited[100005] = { false };
 
-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;
-	}
+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> dist(N);
+	dist[s] = 0;
+	q.push({{ 0, s }, true});
+	while (!q.empty()) {
+		auto c = q.top().first;
+		bool lt = q.top().second;
+		q.pop();
 
-	// 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);
+		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;
+			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;
 	}
-	visited[c.second] = false;
+	return dist[N-1];
 }
 
 int main() {
@@ -30,18 +50,21 @@ int main() {
 	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 });
+		if (ai > bi) {
+			graph[ai].first.push_back({ di, bi });
+			graph[bi].second.push_back({ di, ai });
+		} else {
+			graph[ai].second.push_back({ di, bi });
+			graph[bi].first.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;
+	// long long shortest = 1000000005;
+	// dfs(0, 0, true, shortest);
+	// cout << shortest << endl;
+	cout << dijkstra(0) << endl;
 }