Shortest Distance After Road Addition Queries I

This approach recalculates the shortest paths between all pairs of cities after each query using the Floyd-Warshall algorithm. While it correctly finds the shortest path from city 0 to city n-1, it's highly inefficient because it computes much more information than required.

• For each query i from 0 to queries.length - 1:
  1. Create an n x n distance matrix dist, initialized with infinity, except for dist[j][j] = 0.
  2. Populate dist with initial edges: dist[j][j+1] = 1 for 0 <= j < n-1.
  3. Populate dist with query edges from 0 to i: dist[u][v] = 1 for each query [u, v].
  4. Apply the Floyd-Warshall algorithm to compute all-pairs shortest paths.
  5. Store dist[0][n-1] as the answer for query i.

The Floyd-Warshall algorithm is a dynamic programming approach to find the shortest paths between all pairs of vertices in a weighted directed graph. For each query, we construct a distance matrix representing the graph at that stage. The algorithm works as follows:

1. Initialize an n x n distance matrix dist. dist[i][j] is 1 if there's a direct road from i to j, 0 if i == j, and infinity otherwise.
2. The initial roads i -> i+1 are added to the matrix.
3. For the k-th query, all roads from queries[0] to queries[k] are added.
4. The Floyd-Warshall algorithm is then run on this matrix. It iterates through all possible intermediate vertices k for each pair of source i and destination j, and updates the shortest path dist[i][j] if the path through k is shorter.
5. After the algorithm completes, dist[0][n-1] contains the length of the shortest path from city 0 to city n-1. This process is repeated for every single query.

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int[] answer = new int[queries.length];
        java.util.List<int[]> currentEdges = new java.util.ArrayList<>();

        for (int i = 0; i < queries.length; i++) {
            currentEdges.add(queries[i]);
            
            long[][] dist = new long[n][n];
            for (int r = 0; r < n; r++) {
                java.util.Arrays.fill(dist[r], Integer.MAX_VALUE);
                dist[r][r] = 0;
            }

            // Add initial edges
            for (int j = 0; j < n - 1; j++) {
                dist[j][j + 1] = 1;
            }

            // Add query edges
            for (int[] edge : currentEdges) {
                dist[edge[0]][edge[1]] = 1;
            }

            // Floyd-Warshall algorithm
            for (int k = 0; k < n; k++) {
                for (int u = 0; u < n; u++) {
                    for (int v = 0; v < n; v++) {
                        if (dist[u][k] != Integer.MAX_VALUE && dist[k][v] != Integer.MAX_VALUE) {
                            dist[u][v] = Math.min(dist[u][v], dist[u][k] + dist[k][v]);
                        }
                    }
                }
            }
            answer[i] = (int) dist[0][n - 1];
        }
        return answer;
    }
}