We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Distance After Road Addition Queries II

Difficulty: Hard

Problem Description

You are given an integer n and a 2D integer array queries. There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1. queries[i] = [u_i, v_i] represents the addition of a new unidirectional road from city u_i to city v_i. After each query, you need to find the length of the shortest path from city 0 to city n - 1. Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

Key Insights

  • The problem can be viewed as a dynamic graph where we add edges incrementally.
  • The initial shortest path from city 0 to city n - 1 is n - 1 (via the unidirectional roads).
  • Each query adds a shortcut that can potentially reduce the shortest path.
  • The constraints suggest that the queries are non-overlapping in terms of starting and ending cities, which simplifies pathfinding.

Space and Time Complexity

Time Complexity: O(q * log(n)), where q is the number of queries, due to the need to manage the updated paths efficiently. Space Complexity: O(n), to store the graph's adjacency list.

Solution

To solve this problem, we can use a combination of a graph representation and a priority queue (or a similar structure) to manage the shortest paths dynamically as new roads are added. The algorithm involves maintaining a list of distances from the starting city (city 0) to all other cities and updating these distances as new roads are added.

  1. Initialize an array dist of size n, where dist[i] represents the shortest distance from city 0 to city i. Set dist[0] = 0 and dist[i] = inf for all other cities.
  2. Process each query:
    • For each new road added (from u to v), check if the new distance from city 0 to v through u is shorter than the current known distance.
    • Update the dist array accordingly.
    • Record the shortest distance from city 0 to city n - 1 after each query.
  3. Return the list of distances.

Code Solutions

def shortestDistance(n, queries):
    # Initialize distances
    dist = [float('inf')] * n
    dist[0] = 0  # Distance to start city is 0
    answer = []
    
    # Process each query
    for u, v in queries:
        # Update distance if the new road offers a shorter path
        if dist[u] + 1 < dist[v]:
            dist[v] = dist[u] + 1
            
        # The shortest distance to city n - 1
        answer.append(dist[n - 1] if dist[n - 1] != float('inf') else -1)
        
    return answer
← Back to All Questions