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

难度: Medium

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

返回能通过某些路径到达其他城市数目最少、且路径距离最大为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

示例 1：

输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2] 
城市 1 -> [城市 0, 城市 2, 城市 3] 
城市 2 -> [城市 0, 城市 1, 城市 3] 
城市 3 -> [城市 1, 城市 2] 
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。

示例 2：

输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。 
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1] 
城市 1 -> [城市 0, 城市 4] 
城市 2 -> [城市 3, 城市 4] 
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3] 
城市 0 在阈值距离 2 以内只有 1 个邻居城市。

提示：

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i, distanceThreshold <= 10^4
所有 (from_i, to_i) 都是不同的。

Submission

运行时间: 101 ms

内存: 17.5 MB

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        e = [[] for _ in range(n)]
        for x, y, c in edges:
            e[x].append((y,c))
            e[y].append((x,c))
        ans = [-1]*n
        for i in range(n):
            d = [inf]*n
            d[i] = 0
            q = [(0,i)]
            while q:
                dis, x = heappop(q)
                if dis>d[x]:
                    continue
                ans[i] += 1
                for y, c in e[x]:
                    if (new_d:=dis+c)<d[y] and new_d<=distanceThreshold:
                        d[y] = new_d
                        heappush(q, (d[y], y))
        mn = min(ans)
        for i in range(n-1,-1,-1):
            if ans[i] == mn:
                return i

Explain

本题解采用了Dijkstra算法的变体来解决问题。对于每个城市i，我们使用Dijkstra算法来找到从城市i出发到达所有其他城市的最短路径长度，并记录下来。在这个过程中，我们只考虑那些路径长度不超过distanceThreshold的城市。最后，我们找到那个能够到达其他城市数量最少的城市，如果有多个这样的城市，返回编号最大的那个。

时间复杂度: O(n^3logn)

空间复杂度: O(n^2)

# 增加了注释的题解代码

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        e = [[] for _ in range(n)]
        for x, y, c in edges:
            e[x].append((y,c))
            e[y].append((x,c))
        ans = [-1]*n
        for i in range(n):
            d = [inf]*n
            d[i] = 0
            q = [(0,i)]
            while q:
                dis, x = heappop(q)
                if dis>d[x]:
                    continue
                ans[i] += 1
                for y, c in e[x]:
                    if (new_d:=dis+c)<d[y] and new_d<=distanceThreshold:
                        d[y] = new_d
                        heappush(q, (d[y], y))
        mn = min(ans)
        for i in range(n-1,-1,-1):
            if ans[i] == mn:
                return i

Explore

Dijkstra算法的核心在于每次从未处理的节点中选择一个距离起始节点最短的节点进行扩展。使用优先队列（小顶堆）可以高效地实现这一点。优先队列能够保证在任何时候都快速地访问到当前未访问节点中距离最小的节点。当使用普通队列时，每次寻找最小距离节点需要O(n)时间；而使用小顶堆后，插入操作和删除最小元素的操作平均时间复杂度是O(log n)，大大提升了算法整体的效率，特别是在节点和边很多的情况下更显著。

在题解的代码中，这个条件是通过在更新节点最短路径时加入一个额外的判断来实现的。具体地，当计算到某个邻接节点y的新的可能路径长度new_d时，除了比较new_d是否小于已知的最短距离d[y]，还额外检查new_d是否小于等于distanceThreshold。只有当这两个条件都满足时，才会更新节点y的最短路径长度并将其加入优先队列中继续处理。这确保了算法只考虑那些路径长度不超过给定阈值的城市。

不会影响。题目的目标是找到在给定距离阈值内可达的邻居城市数量最少的城市。因此，只关心在distanceThreshold范围内可达的城市。如果某个城市的路径长度超过了distanceThreshold，这意味着它不应该被计入任何城市的邻居城市数量中。因此，忽略这些城市是符合题目要求的，并不会影响结果的正确性。

在代码中，这个逻辑是通过在找到最少邻居数量后反向遍历城市列表来实现的。具体地，首先计算每个城市的可达邻居数量，并找出最小的邻居数量。然后，代码从最后一个城市开始向前遍历（即从编号最大的城市向编号最小的城市遍历），第一个其邻居数量等于最小邻居数量的城市就是结果。这样，如果有多个城市的邻居数量相同并且都是最小的，返回的将是编号最大的那个城市。