- Define the priority key and whether the smallest or largest item should lead.
- Push each candidate when it becomes eligible.
- Discard stale entries when necessary and process the best live candidate.
Code notes
- 43 lines of Python from the credited upstream file 2203.py.
- The implementation visibly relies on sequence storage, work queue.
- No explicit loop blocks detected.
Complexity
Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def minimumWeight(3 self,4 n: int,5 edges: list[list[int]],6 src1: int,7 src2: int,8 dest: int,9 ) -> int:10 graph = [[] for _ in range(n)]11 reversedGraph = [[] for _ in range(n)]12 13 for u, v, w in edges:14 graph[u].append((v, w))15 reversedGraph[v].append((u, w))16 17 fromSrc1 = self._dijkstra(graph, src1)18 fromSrc2 = self._dijkstra(graph, src2)19 fromDest = self._dijkstra(reversedGraph, dest)20 minWeight = min(a + b + c for a, b, c in zip(fromSrc1, fromSrc2, fromDest))21 return -1 if minWeight == math.inf else minWeight22 23 def _dijkstra(24 self,25 graph: list[list[tuple[int, int]]],26 src: int,27 ) -> list[int]:28 dist = [math.inf] * len(graph)29 30 dist[src] = 031 minHeap = [(dist[src], src)] 32 33 while minHeap:34 d, u = heapq.heappop(minHeap)35 if d > dist[u]:36 continue37 for v, w in graph[u]:38 if d + w < dist[v]:39 dist[v] = d + w40 heapq.heappush(minHeap, (dist[v], v))41 42 return dist43