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

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

floyd

class Solution { public: int findTheCity(int n, vector<vector>& edges, int distanceThreshold) { vector<vector> grid(n, vector(n, 10005)); // 因为边的最大距离是10^4

    // 节点到自己的距离为0
    for (int i = 0; i < n; i++) grid[i][i] = 0;
    // 构造邻接矩阵
    for (const vector<int>& e : edges) {
        int from = e[0];
        int to = e[1];
        int val = e[2];
        grid[from][to] = val;
        grid[to][from] = val; // 注意这里是双向图
    }

    // 开始 floyd
    // 思考 为什么 p 要放在最外面一层
    for (int p = 0; p < n; p++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = min(grid[i][j], grid[i][p] + grid[p][j]);
            }
        }
    }

    int result = 0;
    int count = n + 10; // 记录所有城市在范围内连接的最小城市数量
    for (int i = 0; i < n; i++) {
        int curCount = 0; // 统计一个城市在范围内可以连接几个城市
        for (int j = 0; j < n; j++) {
            if (i != j && grid[i][j] <= distanceThreshold) curCount++;
            // cout << "i:" << i << ", j:" << j << ", val: " << grid[i][j] << endl;
        }
        if (curCount <= count) { // 注意这里是 <=
            count = curCount;
            result = i;
        }
    }
    return result;
}

};