Minimum Weighted Subgraph With the Required Paths LeetCode solution in Python

1
class Solution:
2
    def minimumWeight(self, n, edges, s1, s2, dest):
3
        G1 = defaultdict(list)
4
        G2 = defaultdict(list)
5
        for a, b, w in edges:
6
            G1[a].append((b, w))
7
            G2[b].append((a, w))
8

9
        def Dijkstra(graph, K):
10
            q, t = [(0, K)], {}
11
            while q:
12
                time, node = heappop(q)
13
                if node not in t:
14
                    t[node] = time
15
                    for v, w in graph[node]:
16
                        heappush(q, (time + w, v))
17
            return [t.get(i, float("inf")) for i in range(n)]
18

19
        arr1 = Dijkstra(G1, s1)
20
        arr2 = Dijkstra(G1, s2)
21
        arr3 = Dijkstra(G2, dest)
22

23
        ans = float("inf")
24
        for i in range(n):
25
            ans = min(ans, arr1[i] + arr2[i] + arr3[i])
26

27
        return ans if ans != float("inf") else -1