Medium

题目描述

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

提示：

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

解题思路

这道题需要找到能够到达其他城市数量最少的城市。核心思路是计算任意两点间的最短距离，然后统计每个城市在阈值距离内能到达的城市数量。

解法一：Floyd-Warshall算法（推荐） 使用Floyd-Warshall算法计算所有点对间的最短距离。该算法通过动态规划思想，逐步更新任意两点间的最短路径。时间复杂度O(n³)，对于n≤100的约束条件非常适合。

解法二：多次Dijkstra算法 从每个城市出发运行Dijkstra算法，计算到其他所有城市的最短距离。由于边权非负，Dijkstra算法保证正确性。时间复杂度O(n²logn)。

算法步骤：

  1. 初始化距离矩阵，同城市距离为0，有边的城市距离为边权，其余为无穷大
  2. 使用Floyd-Warshall算法更新最短距离
  3. 统计每个城市在阈值距离内能到达的城市数量
  4. 找到邻居数量最少的城市，如果有多个则选择编号最大的

由于题目要求返回编号最大的城市（当邻居数量相同时），我们从后往前遍历，这样能自然地选择更大的编号。

代码实现

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        // 初始化距离矩阵
        vector<vector<int>> dist(n, vector<int>(n, 1e9));
        
        // 初始化自身距离为0
        for (int i = 0; i < n; i++) {
            dist[i][i] = 0;
        }
        
        // 添加边
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            dist[u][v] = dist[v][u] = w;
        }
        
        // Floyd-Warshall算法
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        int minCount = n;
        int result = 0;
        
        // 统计每个城市的邻居数量
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] <= distanceThreshold) {
                    count++;
                }
            }
            // 选择邻居数量最少的城市，如果相同则选择编号更大的
            if (count <= minCount) {
                minCount = count;
                result = i;
            }
        }
        
        return result;
    }
};

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # 初始化距离矩阵
        dist = [[float('inf')] * n for _ in range(n)]
        
        # 初始化自身距离为0
        for i in range(n):
            dist[i][i] = 0
        
        # 添加边
        for u, v, w in edges:
            dist[u][v] = dist[v][u] = w
        
        # Floyd-Warshall算法
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        min_count = n
        result = 0
        
        # 统计每个城市的邻居数量
        for i in range(n):
            count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
            # 选择邻居数量最少的城市，如果相同则选择编号更大的
            if count <= min_count:
                min_count = count
                result = i
        
        return result

public class Solution {
    public int FindTheCity(int n, int[][] edges, int distanceThreshold) {
        // 初始化距离矩阵
        int[,] dist = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = i == j ? 0 : int.MaxValue;
            }
        }
        
        // 添加边
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            dist[u, v] = dist[v, u] = w;
        }
        
        // Floyd-Warshall算法
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue &&
                        dist[i, k] + dist[k, j] < dist[i, j]) {
                        dist[i, j] = dist[i, k] + dist[k, j];
                    }
                }
            }
        }
        
        int minCount = n;
        int result = 0;
        
        // 统计每个城市的邻居数量
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i, j] <= distanceThreshold) {
                    count++;
                }
            }
            // 选择邻居数量最少的城市，如果相同则选择编号更大的
            if (count <= minCount) {
                minCount = count;
                result = i;
            }
        }
        
        return result;
    }
}

var findTheCity = function(n, edges, distanceThreshold) {
    // 初始化距离矩阵
    const dist = Array(n).fill(null).map(() => Array(n).fill(Infinity));
    
    // 初始化自身距离为0
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    
    // 添加边
    for (const [u, v, w] of edges) {
        dist[u][v] = dist[v][u] = w;
    }
    
    // Floyd-Warshall算法
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    let minCount = n;
    let result = 0;
    
    // 统计每个城市的邻居数量
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (i !== j && dist[i][j] <= distanceThreshold) {
                count++;
            }
        }
        // 选择邻居数量最少的城市，如果相同则选择编号更大的
        if (count <= minCount) {
            minCount = count;
            result = i;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
Floyd-WarshallO(n³)O(n²)
多次DijkstraO(n²logn)O(n²)

推荐使用Floyd-Warshall算法，因为：

  1. 代码实现简洁
  2. 对于n≤100的约束，O(n³)时间复杂度完全可接受
  3. 能够一次性计算所有点对间的最短距离

相关题目