LeetCode 2203: Minimum Weighted Subgraph With the Required Paths Solution

Master LeetCode problem 2203 (Minimum Weighted Subgraph With the Required Paths), 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.

2203. Minimum Weighted Subgraph With the Required Paths

Hard

Graph Shortest Path

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the shortest paths from both src1 and src2 to all other nodes in the graph. Then, we iterate through all edges and check if there exists a subgraph where both src1 and src2 can reach dest by following the edges of the subgraph. We keep track of the minimum weight subgraph that satisfies the conditions. If such a subgraph is found, we return its total weight. Otherwise, we return -1.

Construct the graph using the given edges.
Run Dijkstra's algorithm twice, once starting from src1 and once from src2 to find the shortest paths to all nodes.
Iterate through all edges and check if there exists a valid subgraph connecting src1 and src2 to dest.
Return the minimum weight of such a subgraph if found, else return -1.

Time complexity: O(ElogV) where E is the number of edges and V is the number of vertices. Space complexity: O(V^2) for storing the graph and O(V) for maintaining the priority queue in Dijkstra's algorithm.

Solution Code

import java.util.*;

class Solution {
    public int minWeight(int n, int[][] edges, int src1, int src2, int dest) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        int[] dist1 = dijkstra(graph, src1, n);
        int[] dist2 = dijkstra(graph, src2, n);
        
        int minWeight = Integer.MAX_VALUE;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist1[u] != Integer.MAX_VALUE && dist2[v] != Integer.MAX_VALUE) {
                if (dist1[u] + dist2[v] + w < minWeight && dist1[dest] != Integer.MAX_VALUE && dist2[dest] != Integer.MAX_VALUE) {
                    minWeight = dist1[u] + dist2[v] + w;
                }
            }
        }
        
        return minWeight == Integer.MAX_VALUE ? -1 : minWeight;
    }
    
    private int[] dijkstra(Map<Integer, List<int[]>> graph, int src, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{src, 0});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int node = curr[0];
            int weight = curr[1];
            
            if (weight > dist[node]) continue;
            
            if (graph.containsKey(node)) {
                for (int[] neighbor : graph.get(node)) {
                    int nextNode = neighbor[0];
                    int nextWeight = neighbor[1];
                    
                    if (dist[node] + nextWeight < dist[nextNode]) {
                        dist[nextNode] = dist[node] + nextWeight;
                        pq.offer(new int[]{nextNode, dist[nextNode]});
                    }
                }
            }
        }
        
        return dist;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2203 (Minimum Weighted Subgraph With the Required Paths)?

This page provides optimized solutions for LeetCode problem 2203 (Minimum Weighted Subgraph With the Required Paths) 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 2203 (Minimum Weighted Subgraph With the Required Paths)?

The time complexity for LeetCode 2203 (Minimum Weighted Subgraph With the Required Paths) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2203 on DevExCode?

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

Back to LeetCode Solutions