Time: 215 ms (34.78%), Space: 45.9 MB (15.95%) - LeetHub

py3-coder · py3-coder · commit 6e116a1dfaf1 · 2024-11-27T23:51:52.000+05:30
diff --git a/3243-shortest-distance-after-road-addition-queries-i/3243-shortest-distance-after-road-addition-queries-i.java b/3243-shortest-distance-after-road-addition-queries-i/3243-shortest-distance-after-road-addition-queries-i.java
@@ -0,0 +1,42 @@
+class Solution {
+    private List<List<int[]>> graph;
+
+    private int dijkstra(int n) {
+        int[] dist = new int[n];
+        Arrays.fill(dist, Integer.MAX_VALUE);
+        dist[0] = 0;
+        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
+        pq.offer(new int[]{0, 0});
+
+        while (!pq.isEmpty()) {
+            int[] ele = pq.poll();
+            int cd = ele[0], node = ele[1];
+            if (node == n - 1) return dist[n - 1];
+            if (cd > dist[node]) continue;
+            for (int[] neighbor : graph.get(node)) {
+                int nbr = neighbor[0], wt = neighbor[1];
+                if (cd + wt < dist[nbr]) {
+                    dist[nbr] = cd + wt;
+                    pq.offer(new int[]{cd + wt, nbr});
+                }
+            }
+        }
+        return dist[n - 1];
+    }
+
+    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
+        graph = new ArrayList<>();
+        for (int i = 0; i < n; i++) {
+            graph.add(new ArrayList<>());
+        }
+        for (int i = 0; i < n - 1; i++) {
+            graph.get(i).add(new int[]{i + 1, 1});
+        }
+        List<Integer> res = new ArrayList<>();
+        for (int[] query : queries) {
+            graph.get(query[0]).add(new int[]{query[1], 1});
+            res.add(dijkstra(n));
+        }
+        return res.stream().mapToInt(i -> i).toArray();
+    }
+}
