Shortest Distance After Road Addition Queries II

1. Initialize an adjacency list to represent the graph. Add the initial roads i -> i+1 for all 0 <= i < n-1.
2. Create an array answer to store the results.
3. Iterate through each query [u, v]: a. Add the new directed edge u -> v to the adjacency list. b. Perform a BFS starting from the source city 0: i. Initialize a distance array of size n with a value indicating infinity (e.g., -1), and set distance[0] = 0. ii. Use a queue for BFS and add 0 to it. iii. While the queue is not empty, dequeue a city curr. If curr is n-1, we have found the shortest path length. iv. For each neighbor of curr, if it hasn't been visited (i.e., its distance is infinity), update its distance and enqueue it. c. After the BFS completes, distance[n-1] will hold the length of the shortest path from 0 to n-1. Store this value in the answer array.
4. Return the answer array.

Algorithm:

1. Initialize an adjacency list to represent the graph. Add the initial roads i -> i+1 for all 0 <= i < n-1.
2. Create an array answer to store the results.
3. Iterate through each query [u, v]: a. Add the new directed edge u -> v to the adjacency list. b. Perform a BFS starting from the source city 0: i. Initialize a distance array of size n with a value indicating infinity (e.g., -1), and set distance[0] = 0. ii. Use a queue for BFS and add 0 to it. iii. While the queue is not empty, dequeue a city curr. If curr is n-1, we have found the shortest path length. iv. For each neighbor of curr, if it hasn't been visited (i.e., its distance is infinity), update its distance and enqueue it. c. After the BFS completes, distance[n-1] will hold the length of the shortest path from 0 to n-1. Store this value in the answer array.
4. Return the answer array.

Code Snippet:

1class Solution {2    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {3        List<List<Integer>> adj = new ArrayList<>();4        for (int i = 0; i < n; i++) {5            adj.add(new ArrayList<>());6        }7        for (int i = 0; i < n - 1; i++) {8            adj.get(i).add(i + 1);9        }10 11        int[] result = new int[queries.length];12        for (int i = 0; i < queries.length; i++) {13            adj.get(queries[i][0]).add(queries[i][1]);14 15            int[] dist = new int[n];16            Arrays.fill(dist, -1);17            Queue<Integer> q = new LinkedList<>();18 19            dist[0] = 0;20            q.add(0);21 22            int pathLength = -1;23            while (!q.isEmpty()) {24                int u = q.poll();25                if (u == n - 1) {26                    pathLength = dist[u];27                    break;28                }29                for (int v : adj.get(u)) {30                    if (dist[v] == -1) {31                        dist[v] = dist[u] + 1;32                        q.add(v);33                    }34                }35            }36            result[i] = pathLength;37        }38        return result;39    }40}

1. Initialize an empty list of query edges seen so far.
2. For each new query [u, v]: a. Add the query to the list of edges. b. Create a dist array of size n to compute the new shortest paths. c. Set dist[0] = 0. d. Iterate from i = 1 to n-1 to compute dist[i]: i. The default path is from i-1, so initialize dist[i] = dist[i-1] + 1. ii. Consider all query edges (u_j, v_j) added so far where v_j == i. For each such edge, there's a potential shorter path through u_j. Update dist[i] = min(dist[i], dist[u_j] + 1). e. The shortest path to n-1 is dist[n-1]. Add it to the results.

Algorithm:

1. Initialize an empty list of query edges seen so far.
2. For each new query [u, v]: a. Add the query to the list of edges. b. Create a dist array of size n to compute the new shortest paths. c. Set dist[0] = 0. d. Iterate from i = 1 to n-1 to compute dist[i]: i. The default path is from i-1, so initialize dist[i] = dist[i-1] + 1. ii. Consider all query edges (u_j, v_j) added so far where v_j == i. For each such edge, there's a potential shorter path through u_j. Update dist[i] = min(dist[i], dist[u_j] + 1). e. The shortest path to n-1 is dist[n-1]. Add it to the results.

This approach re-calculates the entire dist array for each query, but it's slightly more optimized than a full BFS as it avoids explicit graph traversal overhead.

Code Snippet:

1class Solution {2    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {3        int[] result = new int[queries.length];4        List<int[]> currentQueries = new ArrayList<>();5 6        for (int i = 0; i < queries.length; i++) {7            currentQueries.add(queries[i]);8            9            Map<Integer, List<Integer>> incomingEdges = new HashMap<>();10            for (int[] q : currentQueries) {11                incomingEdges.computeIfAbsent(q[1], k -> new ArrayList<>()).add(q[0]);12            }13 14            long[] dist = new long[n];15            dist[0] = 0;16            for (int j = 1; j < n; j++) {17                dist[j] = dist[j - 1] + 1;18                if (incomingEdges.containsKey(j)) {19                    for (int u : incomingEdges.get(j)) {20                        dist[j] = Math.min(dist[j], dist[u] + 1);21                    }22                }23            }24            result[i] = (int) dist[n - 1];25        }26        return result;27    }28}

We can process queries online. For each query k, we need to find min_{j<k, v_j <= u_k} (dp[j] - v_j). This is a range minimum query. We can use a segment tree for this. The segment tree will be built over city indices 0 to n-1.

1. Initialize a segment tree of size n to handle range minimum queries and point updates. All values are initialized to infinity.
2. Initialize min_overall_cost = infinity to track min_{j=0..k} (dp[j] - v_j).
3. For each query k = (u_k, v_k): a. Query the segment tree for the minimum value in the range [0, u_k]. Let this be m. b. Calculate dp[k] = u_k + 1 + min(0, m). c. Update the segment tree at index v_k with the value dp[k] - v_k. The update operation should be min(current_value, new_value). d. Update the overall minimum: min_overall_cost = min(min_overall_cost, dp[k] - v_k). e. The shortest path from 0 to n-1 after query k is (n-1) + min(0, min_overall_cost). Store this in the answer array.
4. Return the answer array.

DP Formulation:

The shortest path to any city x is dist(0, x). A path can use the initial i -> i+1 roads or any available query shortcuts. A path that uses shortcuts consists of segments of the initial path, connected by query edges. Let dp[k] be the shortest path from 0 to v_k using query k as the last shortcut. This path looks like 0 -> ... -> u_k -> v_k. The length is dist(0, u_k) + 1. The shortest distance dist(0, u_k) is the minimum of taking the straight path (u_k) or using some previous query j (j < k) as a shortcut. If we use query j=(u_j, v_j), the path is 0 -> ... -> v_j -> ... -> u_k, with length dp[j] + (u_k - v_j). We only consider queries where v_j <= u_k. So, dist(0, u_k) = min(u_k, min_{j<k, v_j <= u_k} (dp[j] + u_k - v_j)). Rearranging, dist(0, u_k) = u_k + min(0, min_{j<k, v_j <= u_k} (dp[j] - v_j)). This gives the recurrence: dp[k] = u_k + 1 + min(0, min_{j<k, v_j <= u_k} (dp[j] - v_j)).

Algorithm with Segment Tree:

We can process queries online. For each query k, we need to find min_{j<k, v_j <= u_k} (dp[j] - v_j). This is a range minimum query. We can use a segment tree for this. The segment tree will be built over city indices 0 to n-1.

1. Initialize a segment tree of size n to handle range minimum queries and point updates. All values are initialized to infinity.
2. Initialize min_overall_cost = infinity to track min_{j=0..k} (dp[j] - v_j).
3. For each query k = (u_k, v_k): a. Query the segment tree for the minimum value in the range [0, u_k]. Let this be m. b. Calculate dp[k] = u_k + 1 + min(0, m). c. Update the segment tree at index v_k with the value dp[k] - v_k. The update operation should be min(current_value, new_value). d. Update the overall minimum: min_overall_cost = min(min_overall_cost, dp[k] - v_k). e. The shortest path from 0 to n-1 after query k is (n-1) + min(0, min_overall_cost). Store this in the answer array.
4. Return the answer array.

Code Snippet:

1class Solution {2    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {3        SegmentTree st = new SegmentTree(n);4        int[] result = new int[queries.length];5        long minCostTerm = Long.MAX_VALUE / 2;6 7        for (int i = 0; i < queries.length; i++) {8            int u = queries[i][0];9            int v = queries[i][1];10 11            long m = st.query(0, u);12            long dp_i = (long)u + 1 + Math.min(0, m);13 14            st.update(v, dp_i - v);15 16            minCostTerm = Math.min(minCostTerm, dp_i - v);17            18            result[i] = (int)((long)n - 1 + Math.min(0, minCostTerm));19        }20        return result;21    }22}23 24class SegmentTree {25    long[] tree;26    int n;27    final long INF = Long.MAX_VALUE / 2;28 29    SegmentTree(int size) {30        n = size;31        tree = new long[4 * n];32        Arrays.fill(tree, INF);33    }34 35    void update(int idx, long val) {36        update(1, 0, n - 1, idx, val);37    }38 39    void update(int node, int start, int end, int idx, long val) {40        if (start == end) {41            tree[node] = Math.min(tree[node], val);42            return;43        }44        int mid = start + (end - start) / 2;45        if (start <= idx && idx <= mid) {46            update(2 * node, start, mid, idx, val);47        } else {48            update(2 * node + 1, mid + 1, end, idx, val);49        }50        tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);51    }52 53    long query(int l, int r) {54        return query(1, 0, n - 1, l, r);55    }56 57    long query(int node, int start, int end, int l, int r) {58        if (r < start || end < l) {59            return INF;60        }61        if (l <= start && end <= r) {62            return tree[node];63        }64        int mid = start + (end - start) / 2;65        long p1 = query(2 * node, start, mid, l, r);66        long p2 = query(2 * node + 1, mid + 1, end, l, r);67        return Math.min(p1, p2);68    }69}