1334.阈值距离内邻居最少的城市

链接：1334.阈值距离内邻居最少的城市
难度：Medium
标签：图、动态规划、最短路
简介：有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

题解 1 - python

• 编辑时间：2023-11-14
• 执行用时：268ms
• 内存消耗：17MB
• 编程语言：python
• 解法介绍：迪杰特斯拉短路算法。

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        nodes = [[] for _ in range(n)]
        for edge in edges:
            nodes[edge[0]].append((edge[1], edge[2]))
            nodes[edge[1]].append((edge[0], edge[2]))
        ans = 0
        cnt = inf
        for i in range(n):
            q = [(0, i)]
            used = [False] * n
            cur = -1
            while q:
                d, node = heappop(q)
                if used[node]: continue
                used[node] = True
                cur += 1
                for next_node, next_d in nodes[node]:
                    if not used[next_node] and d + next_d <= distanceThreshold:
                        heappush(q, (d + next_d, next_node))
            if cur <= cnt:
                cnt = cur
                ans = i
        return ans

题解 2 - python

• 编辑时间：2023-11-14
• 执行用时：560ms
• 内存消耗：16.87MB
• 编程语言：python
• 解法介绍：佛洛依德短路算法。

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        d = [[inf] * n for _ in range(n)]
        for i in range(n): d[i][i] = 0
        for edge in edges:
            d[edge[0]][edge[1]] = edge[2]
            d[edge[1]][edge[0]] = edge[2]
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        ans = 0
        cnt = inf
        for i in range(n):
            cur = len(list(filter(lambda o: o <= distanceThreshold, d[i]))) - 1
            if cur <= cnt:
                ans = i
                cnt = cur
        return ans