1、题目

2、思想

直接深搜。
需要注意一点的是，可以不用使用一个vis数组来记录是否遍历过，如果当前的dp[i]值更新了，那么就需要再次更新。

3、代码

from collections import defaultdict
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        print("hello")
        dp = [99999] * (n+1) # 计算每个节点的最短时间
        # vis = [0] * (n+1)
        info = defaultdict(list)
        for i in range(len(times)):
            u,v,w = times[i]
            info[u].append((v,w)) #到节点，以及其时间
        print(info)            
        # 从节点k出发
        dp[k] = 0                
        self.dfs(k,dp,info)
        print(dp)
        if max(dp[1::]) == 99999:
            return -1
        else:
            return max(dp[1::])

    # cut_time 当前花费的时间
    def dfs(self,root,dp,info):
        a = info[root] # 得到当前这个节点的所有相邻节点
        for i in range(len(a)):
            end,spend = a[i]
            if dp[end] > dp[root]+spend:
                dp[end] = dp[root]+spend # 更新
                self.dfs(end,dp,info)