[python] Almost Dijktra, explained
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.\n\n1. If we meet candidate == d
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.\n\n1. If we meet `candidate == dist[neib]`, it means we found one more way to reach node with minimal cost.\n2. If `candidate < dist[neib]`, it means that we found better candidate, so we update distance and put `cnt[neib] = cnt[idx]`.\n\n#### Complexity\nIt is `O((E+V) log V)` for time as classical Dijkstra and `O(E+V)` for space\n\n```python\nclass Solution:\n    def countPaths(self, n, roads):\n        G = defaultdict(list)\n        for x, y, w in roads:\n            G[x].append((y, w))\n            G[y].append((x, w))\n\n        dist = [float(\'inf\')] * n\n        dist[0] = 0\n        cnt = [0]*n\n        cnt[0] = 1\n        heap = [(0, 0)]\n\n        while heap:\n            (min_dist, idx) = heappop(heap)\n            if idx == n-1: return cnt[idx] % (10**9 + 7)\n            for neib, weight in G[idx]:\n                candidate = min_dist + weight\n                if candidate == dist[neib]:\n                    cnt[neib] += cnt[idx]\n\n                elif candidate < dist[neib]:\n                    dist[neib] = candidate\n                    heappush(heap, (weight + min_dist, neib))\n                    cnt[neib] = cnt[idx]\n```
[]