Problem statement

https://binarysearch.com/problems/Unique-Paths-to-Go-Home/

Solution

  1. First run dijkstra to find distances from home.
  2. Use dp on graph to find number of paths.

Complexity

It is O(E log E + V) for time and O(E + V) for space.

Code

class Solution:
    def solve(self, E):
        def Dijkstra(G, K):
            q, t = [(0, K)], {}
            while q:
                time, node = heappop(q)
                if node not in t:
                    t[node] = time
                    for v, w in G[node]:
                        heappush(q, (time + w, v))
            return [t.get(i, float("inf")) for i in range(n)]

        G, n, M = defaultdict(list), 0, 10**9 + 7
        for x, y, w in E:
            G[x] += [(y, w)]
            G[y] += [(x, w)]
            n = max(n, x+1, y+1)

        dist = Dijkstra(G, n - 1)

        @lru_cache(None)
        def dp(i):
            if i == 0: return 1
            ans = 0
            for j, _ in G[i]:
                if dist[j] > dist[i]:
                    ans += dp(j)
            return ans % M

        return dp(n - 1)