[Python3] dfs + dp
\n\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        graph = {}\n        for u, v, time in roads: \n            graph.
\n```\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        graph = {}\n        for u, v, time in roads: \n            graph.setdefault(u, {})[v] = time\n            graph.setdefault(v, {})[u] = time\n            \n        dist = [inf]*n\n        dist[-1] = 0\n        stack = [(n-1, 0)]\n        while stack: \n            x, t = stack.pop()\n            if t == dist[x]: \n                for xx in graph.get(x, {}): \n                    if t + graph[x][xx] < dist[xx]: \n                        dist[xx] = t + graph[x][xx]\n                        stack.append((xx, t + graph[x][xx]))\n                        \n        @cache\n        def fn(x):\n            """Return """\n            if x == n-1: return 1 \n            if dist[x] == inf: return 0 \n            ans = 0 \n            for xx in graph.get(x, {}): \n                if graph[x][xx] + dist[xx] == dist[x]: ans += fn(xx)\n            return ans % 1_000_000_007\n        \n        return fn(0)\n```\n\n```\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        graph = {}\n        for u, v, time in roads: \n            graph.setdefault(u, []).append((v, time))\n            graph.setdefault(v, []).append((u, time))\n        \n        dist = [inf] * n\n        dist[0] = 0\n        ways = [0] * n\n        ways[0] = 1\n        \n        pq = [(0, 0)]\n        while pq: \n            d, u = heappop(pq)\n            if d > dist[-1]: break\n            if d == dist[u]: \n                for v, time in graph.get(u, []): \n                    if dist[u] + time < dist[v]: \n                        dist[v] = dist[u] + time\n                        ways[v] = ways[u]\n                        heappush(pq, (dist[v], v))\n                    elif dist[u] + time == dist[v]: ways[v] += ways[u]\n        return ways[-1] % 1_000_000_007\n```
['Python3']