[数据结构与算法]LeetCode5836 到达目的地的方案数（单源最短路+DP）

• 题目：

https://leetcode-cn.com/contest/biweekly-contest-59/problems/number-of-ways-to-arrive-at-destination/

有 n 个路口，编号 0 .. n-1

某些路口间，有双向道路，为两个路口需要花费的时间

求：从路口 0 到路口 n-1，满足最少时间的总的方案数目

• 题解：

最少时间——单源最短路

满足最少时间的总的方案数——动态规划（通过单源最短路算法可知，路口 n-1 的最短时间，就是所有其它路口的最短时间）

• 源码：

import heapq
import collections
class Solution:
    def countPaths(self, n: int, roads: list[list[int]]) -> int:
        MOD = 10 ** 9 + 7
        INF = float('inf')
        rds = collections.defaultdict(dict)
        for [s,t,d] in roads:
            rds[s][t] = d
            rds[t][s] = d
        del roads
        best = [INF] * n
        ans = [0] * n

        bfsq = [(0,0)]
        best[0] = 0
        ans[0] = 1

        while bfsq:
            (time, node) = heapq.heappop(bfsq)
            if time > best[node]:
                continue
            for t in rds[node].keys():
                new_time = time + rds[node][t]
                if new_time < best[t]:
                    best[t] = new_time
                    ans[t] = ans[node]
                    heapq.heappush(bfsq, (new_time, t))
                elif new_time == best[t]:
                    ans[t] = (ans[t] + ans[node]) % MOD
        return ans[-1]

if __name__ == "__main__":
    print(Solution().countPaths(n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]))
    print(Solution().countPaths(n = 2, roads = [[1,0,10]]))
    print(Solution().countPaths(n = 1, roads = []))