Problem statement

https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/

Solution

The idea of this problem is to use Dijkstra algorithm, but also we need to keep not only distances to nodes, but counts as well.

  1. If we meet candidate == dist[neib], it means we found one more way to reach node with minimal cost.
  2. If candidate < dist[neib], it means that we found better candidate, so we update distance and put cnt[neib] = cnt[idx].

Complexity

It is O((E+V) log V) for time as classical Dijkstra and O(E+V) for space

class Solution:
    def countPaths(self, n, roads):
        G = defaultdict(list)
        for x, y, w in roads:
            G[x].append((y, w))
            G[y].append((x, w))

        dist = [float('inf')] * n
        dist[0] = 0
        cnt = [0]*n
        cnt[0] = 1
        heap = [(0, 0)]

        while heap:
            (min_dist, idx) = heappop(heap)
            if idx == n-1: return cnt[idx] % (10**9 + 7)
            for neib, weight in G[idx]:
                cand = min_dist + weight
                if cand == dist[neib]:
                    cnt[neib] += cnt[idx]

                elif candidate < dist[neib]:
                    dist[neib] = cand
                    heappush(heap, (cand, neib))
                    cnt[neib] = cnt[idx]