跳转至

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

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回在路径距离限制为 distanceThreshold 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号最大的城市。

题解

此题需要求出任意两点之间的最短路。

Floyd算法

较为简洁的写法是Floyd算法。其核心思想是：

  • 如果令 k 作为顶点 i 和 j 之间路径的中介点能够得到一条更短的路径，则令 k 作为其最短路径的中介点。

本题的代码：

class Solution:
    def findTheCity(
        self, n: int, edges: List[List[int]], distanceThreshold: int
    ) -> int:
        # 初始化
        inf = float("inf")
        dist = [[inf for _ in range(n)] for _ in range(n)]
        for i in range(n): # 自己到自己
            dist[i][i] = 0
        for source, target, v in edges: # 对称初始化
            dist[source][target] = v
            dist[target][source] = v
        # 尝试用k作为中介点来松弛，计算任意节点之间的最短路
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        # 计算题目要求的内容
        l = [(i, sum(x <= distanceThreshold for x in dist[i] if x!=0)) for i in range(n)]
        m = inf
        res = None
        for i, s in l:
            if s <= m:
                m = s
                res = i
        return res

Dijsktra算法

当然，最短路问题我们依然可以使用Dijsktra算法，只不过它一次只能求出一个源点到其他点的最短路。

class Solution:
    def findTheCity(
        self, n: int, edges: List[List[int]], distanceThreshold: int
    ) -> int:
        # 初始化
        inf = float("inf")
        dist = [[inf for _ in range(n)] for _ in range(n)]
        for source, target, v in edges:
            dist[source][target] = v
            dist[target][source] = v

        # 以i为源点，实施Dijkstra算法
        for i in range(n):
            dist[i][i] = 0
            d = dist[i] # 注意这是弱引用，仅为了简化写法
            visited = [False for _ in range(n)]
            for j in range(n):
                t = -1
                # 寻找最短的路径
                for k in range(n):
                    if not visited[k] and (t==-1 or d[k] < d[t]):
                        t = k
                # 加入访问的集合
                visited[t] = True
                # 更新距离
                for k in range(n):
                    d[k] = min(d[k], d[t]+dist[t][k])

        # 计算题目要求的内容
        l = [(i, sum(x <= distanceThreshold for x in dist[i] if x!=0)) for i in range(n)]
        m = inf
        res = None
        for i, s in l:
            if s <= m:
                m = s
                res = i
        return res
最后更新: 2025-08-03 03:17:56
创建日期: 2025-08-03 03:17:56

广告

人要恰饭的嘛🤑🤑

评论