From 69c98b39106cc2776f6a4983e548338ac24b5e84 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Wed, 27 Nov 2024 15:36:04 +0100
Subject: simplify dijkstra

---
 content/graph/dijkstra.cpp | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)

(limited to 'content/graph/dijkstra.cpp')

diff --git a/content/graph/dijkstra.cpp b/content/graph/dijkstra.cpp
index 4c1c9d8..ab4bef9 100644
--- a/content/graph/dijkstra.cpp
+++ b/content/graph/dijkstra.cpp
@@ -1,21 +1,18 @@
-using path = pair<ll, int>; //dist, destination
+using Dist = ll;
 
-auto dijkstra(const vector<vector<path>>& adj, int start) {
-	priority_queue<path, vector<path>, greater<path>> pq;
-	vector<ll> dist(ssize(adj), INF);
-	vector<int> prev(ssize(adj), -1);
-	dist[start] = 0; pq.emplace(0, start);
+auto dijkstra(vector<vector<pair<int, Dist>>> &adj, int start) {
+	priority_queue<pair<Dist, int>> pq;
+	vector<Dist> dist(ssize(adj), INF);
+	dist[start] = 0, pq.emplace(0, start);
 
-	while (!pq.empty()) {
-		auto [dv, v] = pq.top(); pq.pop();
-		if (dv > dist[v]) continue; // WICHTIG!
+	while (!empty(pq)) {
+		auto [du, u] = pq.top();
+		du = -du, pq.pop();
+		if (du > dist[u]) continue; // WICHTIG!
 
-		for (auto [du, u] : adj[v]) {
-			ll newDist = dv + du;
-			if (newDist < dist[u]) {
-				dist[u] = newDist;
-				prev[u] = v;
-				pq.emplace(dist[u], u);
-	}}}
-	return dist; //return prev;
+		for (auto [v, d]: adj[u]) {
+			Dist dv = du + d;
+			if (dv < dist[v]) dist[v] = dv, pq.emplace(-dv, v);
+	}}
+	return dist;
 }
-- 
cgit v1.2.3