2203. Minimum Weighted Subgraph With the Required Paths

1import java.util.*;
2
3class Solution {
4    // Define infinity as the maximum value a long can hold.
5    private static final long INFINITY = Long.MAX_VALUE;
6
7    // The minimumWeight method is responsible for finding the minimum total weight
8    // of paths from two sources (src1 and src2) to one destination (dest).
9    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
10        // Initialize adjacency lists for the graph (g) and the reverse graph (rg)
11        List<Pair<Integer, Long>>[] graph = new List[n];
12        List<Pair<Integer, Long>>[] reverseGraph = new List[n];
13        for (int i = 0; i < n; ++i) {
14            graph[i] = new ArrayList<>();
15            reverseGraph[i] = new ArrayList<>();
16        }
17      
18        // Populate the adjacency list for each edge in the graph.
19        for (int[] edge : edges) {
20            int from = edge[0], to = edge[1];
21            long weight = edge[2];
22            graph[from].add(new Pair<>(to, weight));
23            reverseGraph[to].add(new Pair<>(from, weight));
24        }
25      
26        // Run Dijkstra's algorithm to find shortest paths from src1 and src2
27        // in the graph (g) and from dest in the reverse graph (rg).
28        long[] distancesFromSrc1 = dijkstra(graph, src1);
29        long[] distancesFromSrc2 = dijkstra(graph, src2);
30        long[] distancesToDest = dijkstra(reverseGraph, dest);
31      
32        // Initialize answer as -1 to indicate no solution found yet.
33        long answer = -1;
34      
35        // Iterate over all nodes to find the minimum combined distances.
36        for (int i = 0; i < n; ++i) {
37            // Skip if any one of the distances is infinity.
38            if (distancesFromSrc1[i] == INFINITY || distancesFromSrc2[i] == INFINITY || distancesToDest[i] == INFINITY) {
39                continue;
40            }
41          
42            // Calculate the total distance for the current node.
43            long totalDistance = distancesFromSrc1[i] + distancesFromSrc2[i] + distancesToDest[i];
44          
45            // Update the answer if totalDistance is smaller than the current answer.
46            if (answer == -1 || answer > totalDistance) {
47                answer = totalDistance;
48            }
49        }
50      
51        // Return the minimum total weight of the paths found.
52        return answer;
53    }
54
55    // The dijkstra method implements Dijkstra's algorithm to find the shortest paths
56    // from a starting node (startNode) to all other nodes in the graph.
57    private long[] dijkstra(List<Pair<Integer, Long>>[] graph, int startNode) {
58        int n = graph.length;
59        long[] distances = new long[n];
60        Arrays.fill(distances, INFINITY); // Start with all distances set to infinity.
61        distances[startNode] = 0; // Distance to start node is zero.
62      
63        PriorityQueue<Pair<Long, Integer>> queue = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
64        queue.offer(new Pair<>(0L, startNode)); // Add the start node to the priority queue.
65      
66        while (!queue.isEmpty()) {
67            Pair<Long, Integer> current = queue.poll();
68            long currentDistance = current.getKey();
69            int currentNode = current.getValue();
70          
71            // Skip if we have already found a shorter path to this node.
72            if (currentDistance > distances[currentNode]) {
73                continue;
74            }
75          
76            // For each neighbor, update the shortest distance found and add it to the queue.
77            for (Pair<Integer, Long> edge : graph[currentNode]) {
78                int neighbor = edge.getKey();
79                long edgeWeight = edge.getValue();
80                if (distances[neighbor] > distances[currentNode] + edgeWeight) {
81                    distances[neighbor] = distances[currentNode] + edgeWeight;
82                    queue.offer(new Pair<>(distances[neighbor], neighbor));
83                }
84            }
85        }
86      
87        // Return the array of shortest distances from the start node.
88        return distances;
89    }
90}
91

1#include <vector>
2#include <queue>
3
4// A utility class to represent a pair of values: the node and the distance.
5class Pair {
6public:
7    int node;
8    long long distance;
9
10    Pair(int n, long long dist) : node(n), distance(dist) {}
11};
12
13// A utility class to handle pair comparison within the priority queue.
14class ComparePair {
15public:
16    // The comparator for the priority queue to sort pairs based on distance.
17    bool operator()(const Pair& a, const Pair& b) {
18        return a.distance > b.distance;
19    }
20};
21
22class Solution {
23private:
24    const long long INFINITY = LLONG_MAX; // Define infinity as the maximum value a long long can hold.
25
26    // Dijkstra's algorithm to find the shortest paths from a starting node (startNode) to all other nodes in the graph.
27    std::vector<long long> dijkstra(const std::vector<std::vector<Pair>>& graph, int startNode) {
28        int n = graph.size();
29        std::vector<long long> distances(n, INFINITY);
30        distances[startNode] = 0; // Distance to the start node is zero.
31
32        std::priority_queue<Pair, std::vector<Pair>, ComparePair> queue;
33        queue.push(Pair(startNode, 0));
34
35        while (!queue.empty()) {
36            Pair current = queue.top();
37            queue.pop();
38
39            if (current.distance > distances[current.node]) continue;
40
41            for (const Pair& edge : graph[current.node]) {
42                int neighbor = edge.node;
43                long long edgeWeight = edge.distance;
44                if (distances[neighbor] > distances[current.node] + edgeWeight) {
45                    distances[neighbor] = distances[current.node] + edgeWeight;
46                    queue.push(Pair(neighbor, distances[neighbor]));
47                }
48            }
49        }
50
51        return distances;
52    }
53
54public:
55    long long minimumWeight(int n, std::vector<std::vector<int>>& edges, int src1, int src2, int dest) {
56        // Initialize adjacency lists for the graph and the reverse graph
57        std::vector<std::vector<Pair>> graph(n);
58        std::vector<std::vector<Pair>> reverseGraph(n);
59
60        for (const auto& edge : edges) {
61            int from = edge[0], to = edge[1];
62            long long weight = static_cast<long long>(edge[2]);
63            graph[from].push_back(Pair(to, weight));
64            reverseGraph[to].push_back(Pair(from, weight));
65        }
66
67        // Shortest paths from sources to all nodes
68        std::vector<long long> distancesFromSrc1 = dijkstra(graph, src1);
69        std::vector<long long> distancesFromSrc2 = dijkstra(graph, src2);
70        // Shortest paths from all nodes to the destination
71        std::vector<long long> distancesToDest = dijkstra(reverseGraph, dest);
72
73        long long answer = -1;
74
75        // Iterate over all nodes to find the minimum combined distances
76        for (int i = 0; i < n; ++i) {
77            if (distancesFromSrc1[i] == INFINITY || distancesFromSrc2[i] == INFINITY || distancesToDest[i] == INFINITY) {
78                continue;
79            }
80
81            long long totalDistance = distancesFromSrc1[i] + distancesFromSrc2[i] + distancesToDest[i];
82
83            if (answer == -1 || answer > totalDistance) {
84                answer = totalDistance;
85            }
86        }
87
88        return answer;
89    }
90};
91

1type Pair = {
2  first: number;
3  second: number;
4};
5
6const INFINITY: number = Number.MAX_SAFE_INTEGER; // Define infinity as the maximum safe value a number can hold in JS/TS.
7
8// The minimumWeight function is responsible for finding the minimum total weight
9// of paths from two sources (src1 and src2) to one destination (dest).
10function minimumWeight(n: number, edges: number[][], src1: number, src2: number, dest: number): number {
11  // Initialize adjacency lists for the graph and the reverse graph
12  let graph: Pair[][] = new Array(n);
13  let reverseGraph: Pair[][] = new Array(n);
14  for (let i = 0; i < n; ++i) {
15    graph[i] = [];
16    reverseGraph[i] = [];
17  }
18
19  // Populate the adjacency list for each edge in the graph.
20  edges.forEach((edge) => {
21    const [from, to, weight] = edge;
22    graph[from].push({ first: to, second: weight });
23    reverseGraph[to].push({ first: from, second: weight });
24  });
25
26  // Run Dijkstra's algorithm to find shortest paths from src1 and src2
27  // in the graph and from dest in the reverse graph.
28  let distancesFromSrc1: number[] = dijkstra(graph, src1);
29  let distancesFromSrc2: number[] = dijkstra(graph, src2);
30  let distancesToDest: number[] = dijkstra(reverseGraph, dest);
31
32  // Initialize answer as -1 to indicate no solution found yet.
33  let answer: number = -1;
34
35  // Iterate over all nodes to find the minimum combined distances.
36  for (let i = 0; i < n; ++i) {
37    // Skip if any one of the distances is infinity.
38    if (distancesFromSrc1[i] === INFINITY || distancesFromSrc2[i] === INFINITY || distancesToDest[i] === INFINITY) {
39      continue;
40    }
41  
42    // Calculate the total distance for the current node.
43    let totalDistance: number = distancesFromSrc1[i] + distancesFromSrc2[i] + distancesToDest[i];
44  
45    // Update the answer if totalDistance is smaller than the current answer.
46    if (answer === -1 || answer > totalDistance) {
47      answer = totalDistance;
48    }
49  }
50
51  // Return the minimum total weight of the paths found.
52  return answer;
53}
54
55// The dijkstra function implements Dijkstra's algorithm to find the shortest paths
56// from a starting node to all other nodes in the graph.
57function dijkstra(graph: Pair[][], startNode: number): number[] {
58  let n: number = graph.length;
59  let distances: number[] = new Array(n).fill(INFINITY); // Start with all distances set to infinity.
60  distances[startNode] = 0; // Distance to start node is zero.
61
62  let queue: Pair[] = []; // Use a queue to store nodes and distances.
63  queue.push({ first: 0, second: startNode }); // Add the start node to the priority queue.
64
65  while (queue.length > 0) {
66    // Sort and extract the node with the smallest distance
67    queue.sort((a, b) => a.first - b.first);
68    let current: Pair = queue.shift()!;
69    let currentNode: number = current.second;
70    let currentDistance: number = current.first;
71  
72    // Skip if we have already found a shorter path to this node.
73    if (currentDistance > distances[currentNode]) {
74      continue;
75    }
76  
77    // For each neighbor, update the shortest distance found and add it to the queue.
78    graph[currentNode].forEach((edge: Pair) => {
79      let neighbor: number = edge.first;
80      let edgeWeight: number = edge.second;
81      let newDistance: number = distances[currentNode] + edgeWeight;
82      if (distances[neighbor] > newDistance) {
83        distances[neighbor] = newDistance;
84        queue.push({ first: newDistance, second: neighbor });
85      }
86    });
87  }
88
89  // Return the array of shortest distances from the start node.
90  return distances;
91}
92