6255-两个城市间路径的最小分数

6255. 两个城市间路径的最小分数

• 构建节点之间的关系
• 递归
  • 递归函数的含义：把当前节点加入到已访问列表中，并通过和自己的所有邻居比较，更新全局最小值（一定不要跳进递归，相信这个函数能返回你需要的东西）
  • 这个函数的变量：节点
  • 得到递归结果后，要干什么：更新全局最小值
  • 递归结束的条件：当前节点已经在访问列表中，则 return

from collections import defaultdict


class Solution:
    def __init__(self):
        self.res = float("inf")

    def minScore(self, n,roads):
        m = defaultdict(list) # 用字典保存关系
        # 构建节点之间的关系，注意：一个节点可能有多个邻居
        for a, b, d in roads:
            m[a].append([b, d])
            m[b].append([a, d])

        visit = set() # 用一个集合保存已经遍历过的节点，防止陷入无限循环

        def dfs(node):
            # 递归结束的条件
            if node in visit:
                return

            visit.add(node) # 添加当前节点，表示已经访问过了
            for neighbor, cost in m[node]:
                self.res = min(self.res, cost) # 就当前节点而言，遍历它的邻居，并更新最小值
                dfs(neighbor)# 让邻居递归，相信邻居能继续继续更新self.res

        dfs(1)
        return self.res

其他写法：

class Solution:
    def __init__(self):
        self.ans = float("inf")

    def minScore(self, n, roads):
        g = [[] for _ in range(n)] # 用列表保存关系
        for x, y, d in roads:
            g[x - 1].append([y - 1, d])
            g[y - 1].append([x - 1, d])

        vis = [False] * n

        def dfs(x):
            if vis[x]:
                return
            vis[x] = True
            for y, d in g[x]:
                self.ans = min(self.ans, d)
                dfs(y)
        dfs(0)
        return self.ans