# 2203. Minimum Weighted Subgraph With the Required Paths    • Time: $O(|V|\log |E|)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public: long long minimumWeight(int n, vector>& edges, int src1, int src2, int dest) { vector>> graph1(n); vector>> graph2(n); // reversed(graph1) for (const auto& e : edges) { const int u = e; const int v = e; const int w = e; graph1[u].emplace_back(v, w); graph2[v].emplace_back(u, w); } const auto fromSrc1 = dijkstra(graph1, src1); const auto fromSrc2 = dijkstra(graph1, src2); const auto fromDest = dijkstra(graph2, 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: constexpr static long kMax = 1e10; vector dijkstra(const vector>>& graph, int src) { using P = pair; priority_queue, greater<>> minHeap; // (d, u) vector dist(graph.size(), kMax); minHeap.emplace(0, src); while (!minHeap.empty()) { const auto [d, u] = minHeap.top(); minHeap.pop(); if (dist[u] != kMax) continue; dist[u] = d; for (const auto& [v, w] : graph[u]) minHeap.emplace(d + w, v); } return dist; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 class Solution { public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) { List>[] graph1 = new List[n]; List>[] graph2 = new List[n]; // reversed(graph1) for (int i = 0; i < n; ++i) { graph1[i] = new ArrayList<>(); graph2[i] = new ArrayList<>(); } for (int[] e : edges) { final int u = e; final int v = e; final int w = e; graph1[u].add(new Pair<>(v, w)); graph2[v].add(new Pair<>(u, w)); } long[] fromSrc1 = dijkstra(graph1, src1); long[] fromSrc2 = dijkstra(graph1, src2); long[] fromDest = dijkstra(graph2, 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>[] graph, int src) { Queue> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey)); // (d, u) long[] dist = new long[graph.length]; Arrays.fill(dist, kMax); minHeap.offer(new Pair<>(0L, src)); while (!minHeap.isEmpty()) { final long d = minHeap.peek().getKey(); final int u = minHeap.poll().getValue(); if (dist[u] != kMax) continue; dist[u] = d; for (var node : graph[u]) { final int v = node.getKey(); final int w = node.getValue(); minHeap.offer(new Pair<>(d + w, v)); } } return dist; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int: graph1 = [[] for _ in range(n)] graph2 = [[] for _ in range(n)] # reversed(graph1) for u, v, w in edges: graph1[u].append((v, w)) graph2[v].append((u, w)) def dijkstra(graph: List[List[Tuple[int, int]]], src: int) -> List[int]: minHeap = [(0, src)] # (d, u) dist = [math.inf] * n while minHeap: d, u = heapq.heappop(minHeap) if dist[u] != math.inf: continue dist[u] = d for v, w in graph[u]: heapq.heappush(minHeap, (d + w, v)) return dist fromSrc1 = dijkstra(graph1, src1) fromSrc2 = dijkstra(graph1, src2) fromDest = dijkstra(graph2, dest) minWeight = min(a + b + c for a, b, c in zip(fromSrc1, fromSrc2, fromDest)) return -1 if minWeight == math.inf else minWeight