跳到主要内容

1976.到达目的地的方案数

链接：1976.到达目的地的方案数
难度：Medium
标签：图、拓扑排序、动态规划、最短路
简介：请返回花费 最少时间 到达目的地的 路径数目 。

题解 1 - python​

  • 编辑时间：2024-03-05
  • 执行用时：59ms
  • 内存消耗：23.55MB
  • 编程语言：python
  • 解法介绍：最短路遍历时同时记录当前的最大cnt。
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        nodes = [[] for _ in range(n)]
        for n1, n2, time in roads:
            nodes[n1].append((n2, time))
            nodes[n2].append((n1, time))
        time_map = [inf] * n
        time_map[0] = 0
        cnt_map = [0] * n
        cnt_map[0] = 1
        heap = [(0, 0)]
        while heap:
            time, node = heappop(heap)
            if time > time_map[node]: continue
            for child, time2 in nodes[node]:
                next_time = time + time2
                if next_time == time_map[child]:
                    cnt_map[child] = (cnt_map[node] + cnt_map[child]) % (10 ** 9 + 7)
                elif next_time < time_map[child]:
                    time_map[child] = next_time
                    cnt_map[child] = cnt_map[node]
                    heappush(heap, (next_time, child))
        return cnt_map[n - 1]