Python - Dijkstra's Algorithm (Min Heap Implementation) >90% time score
```\nfrom heapq import *\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        # create adjacency list\n        adj_list =
```\nfrom heapq import *\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        # create adjacency list\n        adj_list = defaultdict(list)\n        for i,j,k in roads:\n            adj_list[i].append((j,k))\n            adj_list[j].append((i,k))\n            \n        start = 0\n        end = n-1\n        \n        # set minimum distance of all nodes but start to infinity.\n        # min_dist[i] = [minimum time from start, number of ways to get to node i in min time]\n        min_dist = {i:[float(\'inf\'),0] for i in adj_list.keys()}\n        min_dist[start] = [0,1]\n             \n        # Heap nodes in the format (elapsed time to get to that node, node index)\n        # This is done so as to allow the heap to pop node with lowest time first\n        # Push first node to heap.\n        heap = [(0, start)]\n        while heap:\n            elapsed_time, node = heappop(heap)\n            # if nodes getting popped have a higher elapsed time than minimum time required\n            # to reach end node, means we have exhausted all possibilities\n            # Note: we can do this only because time elapsed cannot be negetive\n            if elapsed_time > min_dist[end][0]:\n                break\n            for neighbor, time in adj_list[node]:\n                # check most expected condition first. Reduce check time for if statement\n                if (elapsed_time + time) > min_dist[neighbor][0]:\n                    continue\n                # if time is equal to minimum time to node, add the ways to get to node to\n                # the next node in minimum time\n                elif (elapsed_time + time) == min_dist[neighbor][0]:\n                    min_dist[neighbor][1] += min_dist[node][1]\n                else: # node has not been visited before. Set minimum time \n                    min_dist[neighbor][0] = elapsed_time + time\n                    min_dist[neighbor][1] = min_dist[node][1]\n                    heappush(heap, (elapsed_time+time,neighbor))\n\n        return min_dist[end][1]%(pow(10,9)+7)\n        \n
['Graph', 'Heap (Priority Queue)', 'Python', 'Python3']