Problem statement

https://binarysearch.com/problems/Pick-Up-Gold-in-Two-Locations/

Solution

Similar to Leetcode 2203. Minimum Weighted Subgraph With the Required Paths, but here we first need to constuct graph and also subtract 2 times the cost of node x.

Complexity

It is O(nm * log(mn)) for time and O(mn) for space.

Code

class Solution:
    def solve(self, M, r, c, r0, c0, r1, c1):
        def Dijkstra(K):
            q, t = [(0, K)], [-1]*(m*n)
            while q:
                time, node = heappop(q)
                if t[node] == -1:
                    t[node] = time
                    for v, w in G[node]:
                        heappush(q, (time + w, v))
            return t

        n, m = len(M), len(M[0])
        G = defaultdict(list)
        for x, y in product(range(n), range(m)):
            for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
                if 0 <= x + dx < n and 0 <= y + dy < m:
                    G[(x + dx)*m + y + dy] += [(x * m + y, M[x+dx][y+dy])]

        x1 = Dijkstra(r * m + c)
        x2 = Dijkstra(r0 * m + c0)
        x3 = Dijkstra(r1 * m + c1)
        x4 = [M[x][y] for x in range(n) for y in range(m)]
        return min(a + b + c + d for a, b, c, d in zip(x1, x2, x3, x4))