3243. Shortest Distance After Road Addition Queries I | Daily LeetCode Solution

Описание: 👉 Problem Link: https://leetcode.com/problems/shortes...
👉 Solution: Pinned in the comments.

🔍 LeetCode Problem of the Day: 3243. Shortest Distance After Road Addition Queries I | LeetCode Daily Solution

In today’s LeetCode daily challenge, we solve the Shortest Distance After Road Addition Queries I problem using BFS to calculate the shortest path after adding roads dynamically in Java.

🌟 Problem Description:
You are given a graph with n nodes and n-1 roads forming a connected graph. For each query, a new road is added between two nodes, and the task is to compute the shortest distance between node 0 and node n-1 after the addition of the road.

🔑 Key Points:
Graph Representation: We use an adjacency list to represent the graph and dynamically update it with each query.
Breadth-First Search (BFS): After adding a new road, perform BFS to calculate the shortest path from node 0 to node n-1.
Edge Cases: Handle situations where a road addition doesn’t change the shortest path.

📝 Code Explanation:
Graph Initialization: Start with a graph having n nodes and n-1 roads.
BFS Function: Perform BFS from node 0 to calculate the shortest distance to node n-1.
Keep track of visited nodes and their distance from node 0.
Process Queries: For each query, add the new road to the graph and compute the shortest distance using BFS.
Store Results: For each query, store the shortest distance or Integer.MAX_VALUE if node n-1 is unreachable.

💡 Example:
Input:
n = 6
queries = [[0, 3], [4, 5], [2, 3]]
Output:
[2, 3, 2]
Explanation: After each query, the shortest distance from node 0 to node 5 is computed.

📅 Daily Solutions:
Subscribe for daily LeetCode solutions explained step-by-step in Java!

👥 Join the Discussion:
What optimizations can you think of for handling these types of queries? Share your thoughts in the comments!