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] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. 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.
Example 1:
Input: n = 5, queries = [[2,4],[0,2],[0,4]]
Output: [3,2,1]
Explanation:
After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
Example 2:
Input: n = 4, queries = [[0,3],[0,2]]
Output: [1,1]
Explanation:
After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
After the addition of the road from 0 to 2, the length of the shortest path remains 1.
Constraints:
3 <= n <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]This approach treats the problem as a graph traversal problem where each city is a node and roads are directed edges. Initially, the graph is linear, and each query introduces a single directed edge. We can use BFS to update and find the shortest path after each new road is added, recalculating the shortest path from node 0 to node n-1.
This Python function shortest_path accepts the number of cities, n, and the list of queries that represent new road additions. The function maintains a dynamic graph representation and repeatedly performs BFS to determine the new shortest path from city 0 to city n-1 after each query.
JavaScript
Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query.
Space Complexity: O(n + q), accounting for graph representation and BFS queue.
This approach models the problem as a weighted graph and uses Dijkstra's algorithm, which is suitable since the graph predominantly has unit weights. This algorithm efficiently finds the shortest path from the start city to the end city after each new road is introduced, leveraging a priority queue to always expand the shortest known total distance path.
This C++ implementation of Dijkstra's algorithm uses a priority queue to determine the shortest path efficiently. Initially, the graph is set up with each city i and i+1 connected. For each query, a new edge is added, and the Dijkstra's algorithm recalculates the shortest path.
Java
Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query.
Space Complexity: O(n + q), needed for graph representation and distance calculations.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query. |
| Dijkstra's Algorithm with Priority Queue | Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query. |
Shortest Distance After Road Addition Queries I - Leetcode 3243 - Python • NeetCodeIO • 9,635 views views
Watch 9 more video solutions →Practice Shortest Distance After Road Addition Queries I with our built-in code editor and test cases.
Practice on FleetCode