2203. Minimum Weighted Subgraph With the Required Paths LeetCode Solution

In this guide, you will get 2203. Minimum Weighted Subgraph With the Required Paths LeetCode Solution with the best time and space complexity. The solution to Minimum Weighted Subgraph With the Required Paths problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Weighted Subgraph With the Required Paths solution in C++
  4. Minimum Weighted Subgraph With the Required Paths solution in Java
  5. Minimum Weighted Subgraph With the Required Paths solution in Python
  6. Additional Resources
2203. Minimum Weighted Subgraph With the Required Paths LeetCode Solution image

Problem Statement of Minimum Weighted Subgraph With the Required Paths

You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n – 1.
You are also given a 2D integer array edges where edges[i] = [fromi, toi, weighti] denotes that there exists a directed edge from fromi to toi with weight weighti.
Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.
Return the minimum weight of a subgraph of the graph such that it is possible to reach dest from both src1 and src2 via a set of edges of this subgraph. In case such a subgraph does not exist, return -1.
A subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.

See also  1946. Largest Number After Mutating Substring LeetCode Solution

Example 1:

Input: n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
Output: 9
Explanation:
The above figure represents the input graph.
The blue edges represent one of the subgraphs that yield the optimal answer.
Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.

Example 2:

Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
Output: -1
Explanation:
The above figure represents the input graph.
It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.

Constraints:

3 <= n <= 105
0 <= edges.length <= 105
edges[i].length == 3
0 <= fromi, toi, src1, src2, dest <= n – 1
fromi != toi
src1, src2, and dest are pairwise distinct.
1 <= weight[i] <= 105

Complexity Analysis

  • Time Complexity: O(|V|\log |E|)
  • Space Complexity: O(n)

2203. Minimum Weighted Subgraph With the Required Paths LeetCode Solution in C++

class Solution {
 public:
  long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2,
                          int dest) {
    vector<vector<pair<int, int>>> graph(n);
    vector<vector<pair<int, int>>> reversedGraph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      graph[u].emplace_back(v, w);
      reversedGraph[v].emplace_back(u, w);
    }

    const vector<long> fromSrc1 = dijkstra(graph, src1);
    const vector<long> fromSrc2 = dijkstra(graph, src2);
    const vector<long> fromDest = dijkstra(reversedGraph, dest);
    long ans = kMax;

    for (int i = 0; i < n; ++i) {
      if (fromSrc1[i] == kMax || fromSrc2[i] == kMax || fromDest[i] == kMax)
        continue;
      ans = min(ans, fromSrc1[i] + fromSrc2[i] + fromDest[i]);
    }

    return ans == kMax ? -1 : ans;
  }

 private:
  static constexpr long kMax = 10'000'000'000;

  vector<long> dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
    vector<long> dist(graph.size(), kMax);

    dist[src] = 0;
    using P = pair<long, int>;  // (d, u)
    priority_queue<P, vector<P>, greater<>> minHeap;
    minHeap.emplace(dist[src], src);

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (d > dist[u])
        continue;
      for (const auto& [v, w] : graph[u])
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.emplace(dist[v], v);
        }
    }

    return dist;
  }
};
/* code provided by PROGIEZ */

2203. Minimum Weighted Subgraph With the Required Paths LeetCode Solution in Java

class Solution {
  public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
    List<Pair<Integer, Integer>>[] graph = new List[n];
    List<Pair<Integer, Integer>>[] reversedGraph = new List[n];

    for (int i = 0; i < n; ++i) {
      graph[i] = new ArrayList<>();
      reversedGraph[i] = new ArrayList<>();
    }

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      final int w = edge[2];
      graph[u].add(new Pair<>(v, w));
      reversedGraph[v].add(new Pair<>(u, w));
    }

    long[] fromSrc1 = dijkstra(graph, src1);
    long[] fromSrc2 = dijkstra(graph, src2);
    long[] fromDest = dijkstra(reversedGraph, dest);
    long ans = kMax;

    for (int i = 0; i < n; ++i) {
      if (fromSrc1[i] == kMax || fromSrc2[i] == kMax || fromDest[i] == kMax)
        continue;
      ans = Math.min(ans, fromSrc1[i] + fromSrc2[i] + fromDest[i]);
    }

    return ans == kMax ? -1 : ans;
  }

  private static long kMax = (long) 1e10;

  private long[] dijkstra(List<Pair<Integer, Integer>>[] graph, int src) {
    long[] dist = new long[graph.length];
    Arrays.fill(dist, kMax);

    dist[src] = 0;
    Queue<Pair<Long, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey)) {
      {
        offer(new Pair<>(dist[src], src)); // (d, u)
      }
    };

    while (!minHeap.isEmpty()) {
      final long d = minHeap.peek().getKey();
      final int u = minHeap.poll().getValue();
      if (d > dist[u])
        continue;
      for (Pair<Integer, Integer> pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.offer(new Pair<>(dist[v], v));
        }
      }
    }

    return dist;
  }
}
// code provided by PROGIEZ

2203. Minimum Weighted Subgraph With the Required Paths LeetCode Solution in Python

class Solution:
  def minimumWeight(
      self,
      n: int,
      edges: list[list[int]],
      src1: int,
      src2: int,
      dest: int,
  ) -> int:
    graph = [[] for _ in range(n)]
    reversedGraph = [[] for _ in range(n)]

    for u, v, w in edges:
      graph[u].append((v, w))
      reversedGraph[v].append((u, w))

    fromSrc1 = self._dijkstra(graph, src1)
    fromSrc2 = self._dijkstra(graph, src2)
    fromDest = self._dijkstra(reversedGraph, dest)
    minWeight = min(a + b + c for a, b, c in zip(fromSrc1, fromSrc2, fromDest))
    return -1 if minWeight == math.inf else minWeight

  def _dijkstra(
      self,
      graph: list[list[tuple[int, int]]],
      src: int,
  ) -> list[int]:
    dist = [math.inf] * len(graph)

    dist[src] = 0
    minHeap = [(dist[src], src)]  # (d, u)

    while minHeap:
      d, u = heapq.heappop(minHeap)
      if d > dist[u]:
        continue
      for v, w in graph[u]:
        if d + w < dist[v]:
          dist[v] = d + w
          heapq.heappush(minHeap, (dist[v], v))

    return dist
# code by PROGIEZ

Additional Resources

See also  507. Perfect Number LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.