LeetCode 3515: Shortest Path in a Weighted Tree Solution

Master LeetCode problem 3515 (Shortest Path in a Weighted Tree), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3515. Shortest Path in a Weighted Tree

Hard

Array Tree Depth-First Search Binary Indexed Tree Segment Tree

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the shortest path from the root node 1 to each node in the tree. We will maintain a priority queue to process nodes based on their distances from the root node. Initially, all nodes will have a distance of infinity except for the root node with a distance of 0. As we process each node, we update the distances of its neighbors if a shorter path is found.

For the query type 1, we simply update the weight of the specified edge between nodes u and v to the new weight w'. For query type 2, we return the shortest path distance from the root node 1 to node x that we have calculated using Dijkstra's algorithm.

Time Complexity: O(n log n) where n is the number of nodes in the tree Space Complexity: O(n)

Solution Code

import java.util.*;

class Solution {
    public int[] shortestPath(int n, int[][] edges, int[][] queries) {
        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph[u].add(new int[]{v, w});
            graph[v].add(new int[]{u, w});
        }
        
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[]{1, 0});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int node = curr[0];
            int currDist = curr[1];
            if (currDist > dist[node]) continue;
            
            for (int[] neighbor : graph[node]) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];
                if (currDist + weight < dist[nextNode]) {
                    dist[nextNode] = currDist + weight;
                    pq.offer(new int[]{nextNode, dist[nextNode]});
                }
            }
        }
        
        int[] result = new int[queries.length];
        int index = 0;
        for (int[] query : queries) {
            if (query[0] == 1) {
                int u = query[1];
                int v = query[2];
                int newWeight = query[3];
                for (int[] neighbor : graph[u]) {
                    if (neighbor[0] == v) {
                        neighbor[1] = newWeight;
                        break;
                    }
                }
                for (int[] neighbor : graph[v]) {
                    if (neighbor[0] == u) {
                        neighbor[1] = newWeight;
                        break;
                    }
                }
            } else {
                int x = query[1];
                result[index++] = dist[x];
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3515 (Shortest Path in a Weighted Tree)?

This page provides optimized solutions for LeetCode problem 3515 (Shortest Path in a Weighted Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3515 (Shortest Path in a Weighted Tree)?

The time complexity for LeetCode 3515 (Shortest Path in a Weighted Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3515 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3515 in Java, C++, or Python.

Back to LeetCode Solutions