[Python] Dijkstra + DP solution (60-70% faster)
Logic\n- Dijkstra algorithm can only get the shortest time from src to dst.\n- What we want to get is the number of ways with minimum time from src to dst.\n- W
## Logic\n- Dijkstra algorithm can only get the shortest time from src to dst.\n- What we want to get is **the number of ways with minimum time from src to dst.**\n- We need\n\t1) **times** array : to check the minimum time to take from src to times[i].\n\t2) **ways** array : to check the total ways from src to ways[i] within minimum time.\n\n- if find same time path... update **ways** only \n ... because we don\'t need to update time \n ... and we don\'t need to go to that node(already in our heap)\n\n\n## EX1\n**times**    [INF, INF, INF, INF, INF, INF] => [0, 2, 5, 5, 6, 7]\n**ways**      [0, 0, 0, 0, 0, 0] => [1, 1, 1, 1, 1, 2, 4]\n\n\n## Reference\nIdea and code from ... #happycoding\nhttps://www.youtube.com/watch?v=1JCXqupyLoQ&t=465s\n\n\n\n```\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n\n        #1. graph\n        graph = collections.defaultdict(list)\n        for u, v, t in roads:\n            graph[u].append((v, t))\n            graph[v].append((u, t))\n            \n        #2. times, ways array initializer\n        times = [float(\'inf\')] * n\n        ways = [0] * n\n        \n        times[0] = 0\n        ways[0] = 1\n        \n        #3. dijkstra\n        pq = [(0, 0)] # time, node\n        \n        while pq:\n            old_t, u = heapq.heappop(pq) # current time, current node\n            \n            for v, t in graph[u]:\n                new_t = old_t + t\n                \n                # casual logic: update shorter path\n                if new_t < times[v]:\n                    times[v] = new_t\n                    ways[v] = ways[u]\n                    heapq.heappush(pq, (new_t, v))\n                \n                # if find same time path... update ways only\n                elif new_t == times[v]:\n                    ways[v] += ways[u]\n                \n        modulo = 10 ** 9 + 7\n        \n        return ways[n-1] % modulo\n```\n\n**Please upvote if it helped! :)**
['Dynamic Programming', 'Breadth-First Search', 'Python']