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

这道题到底在问什么

输入

n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 阈值=4

输出

3(城市 0 和 3 都只有 2 个近邻,并列取大编号 3)

最优解：一步一步想明白

1. 3记住「中转点 k 放最外层,dist[i][k]+dist[k][j] 更短就松弛」,下面逐帧套它。
2. 4先建一张 4×4 的距离表 dist[i][j] = 城市 i 到 j 的最短距离。对角线(自己到自己)填 0(绿),其余全填 ∞ 表示「还不知道怎么走」。
3. 5把每条边 (a,b,w) 填进去:dist[a][b]=dist[b][a]=w。比如 (0,1,3) 让 dist[0][1]=dist[1][0]=3。现在表里(紫)只有直接相连的距离,不直连的还是 ∞。
4. 6第 0 轮:允许所有路径经过中转点城市 0。逐个看 dist[i][j] 能不能借道 0 变短,也就是比较 dist[i][0] + dist[0][j] 和 dist[i][j]。第 0 行和第 0 列(蓝)就是这一轮的「桥」。
5. 7这一轮借道城市 0 没找到任何更短的路(城市 0 帮不上忙或已是最优),dist 表保持不变。
6. 8第 1 轮:允许所有路径经过中转点城市 1。逐个看 dist[i][j] 能不能借道 1 变短,也就是比较 dist[i][1] + dist[1][j] 和 dist[i][j]。第 1 行和第 1 列(蓝)就是这一轮的「桥」。
7. 9城市 0 到 2:原来是 ∞,但「0→1→2」只要 3 + 1 = 4,更短!更新 dist[0][2] = 4(紫)。两个蓝格就是借的桥 dist[0][1] 和 dist[1][2]。
8. 10城市 0 到 3:原来是 ∞,但「0→1→3」只要 3 + 4 = 7,更短!更新 dist[0][3] = 7(紫)。两个蓝格就是借的桥 dist[0][1] 和 dist[1][3]。
9. 11城市 2 到 0:原来是 ∞,但「2→1→0」只要 1 + 3 = 4,更短!更新 dist[2][0] = 4(紫)。两个蓝格就是借的桥 dist[2][1] 和 dist[1][0]。
10. 12城市 3 到 0:原来是 ∞,但「3→1→0」只要 4 + 3 = 7,更短!更新 dist[3][0] = 7(紫)。两个蓝格就是借的桥 dist[3][1] 和 dist[1][0]。
11. 13第 2 轮:允许所有路径经过中转点城市 2。逐个看 dist[i][j] 能不能借道 2 变短,也就是比较 dist[i][2] + dist[2][j] 和 dist[i][j]。第 2 行和第 2 列(蓝)就是这一轮的「桥」。
12. 14城市 0 到 3:原来是 7,但「0→2→3」只要 4 + 1 = 5,更短!更新 dist[0][3] = 5(紫)。两个蓝格就是借的桥 dist[0][2] 和 dist[2][3]。
13. 15城市 1 到 3:原来是 4,但「1→2→3」只要 1 + 1 = 2,更短!更新 dist[1][3] = 2(紫)。两个蓝格就是借的桥 dist[1][2] 和 dist[2][3]。
14. 16城市 3 到 0:原来是 7,但「3→2→0」只要 1 + 4 = 5,更短!更新 dist[3][0] = 5(紫)。两个蓝格就是借的桥 dist[3][2] 和 dist[2][0]。
15. 17城市 3 到 1:原来是 4,但「3→2→1」只要 1 + 1 = 2,更短!更新 dist[3][1] = 2(紫)。两个蓝格就是借的桥 dist[3][2] 和 dist[2][1]。
16. 18第 3 轮:允许所有路径经过中转点城市 3。逐个看 dist[i][j] 能不能借道 3 变短,也就是比较 dist[i][3] + dist[3][j] 和 dist[i][j]。第 3 行和第 3 列(蓝)就是这一轮的「桥」。
17. 19这一轮借道城市 3 没找到任何更短的路(城市 3 帮不上忙或已是最优),dist 表保持不变。四轮都跑完,dist 已是全源最短路。
18. 20数城市 0 这一行:到其它城市的最短距离里,≤ 4 的有 2 个(绿),分别是 1(3)、2(4)。这就是城市 0 的「阈值内邻居数」。
19. 21数城市 1 这一行:到其它城市的最短距离里,≤ 4 的有 3 个(绿),分别是 0(3)、2(1)、3(2)。这就是城市 1 的「阈值内邻居数」。
20. 22数城市 2 这一行:到其它城市的最短距离里,≤ 4 的有 3 个(绿),分别是 0(4)、1(1)、3(1)。这就是城市 2 的「阈值内邻居数」。
21. 23数城市 3 这一行:到其它城市的最短距离里,≤ 4 的有 2 个(绿),分别是 1(2)、2(1)。这就是城市 3 的「阈值内邻居数」。
22. 24把四座城市的邻居数排开:城市 0 有 2 个,城市 1 有 3 个,城市 2 有 3 个,城市 3 有 2 个。最少是 2 个,城市 0 和城市 3 并列。题目要求并列时取编号最大的,所以答案是城市 3。
23. 25最终答案:城市 3。它在阈值 4 内只有 2 个近邻、并列时编号最大。回头看:整道题的核心就是先用 Floyd 把任意两城的最短距离一次性算全,再简单数一数即可。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        INF = 10**15
        dist = [[INF] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for a, b, w in edges:
            dist[a][b] = dist[b][a] = min(dist[a][b], w)
        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]
        best_city, best_count = -1, 10**9
        for i in range(n):
            cnt = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
            if cnt <= best_count:
                best_count = cnt
                best_city = i
        return best_city

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const int INF = 1e9;
        vector<vector<int>> dist(n, vector<int>(n, INF));
        for (int i = 0; i < n; ++i) dist[i][i] = 0;
        for (auto &e : edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = min(dist[e[0]][e[1]], e[2]);
        for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        int ans = -1, best = INF;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = 0; j < n; ++j) if (i != j && dist[i][j] <= distanceThreshold) cnt++;
            if (cnt <= best) { best = cnt; ans = i; }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (int[] e : edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = Math.min(dist[e[0]][e[1]], e[2]);
        for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        int ans = -1, best = INF;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) if (i != j && dist[i][j] <= distanceThreshold) cnt++;
            if (cnt <= best) { best = cnt; ans = i; }
        }
        return ans;
    }
}

复杂度

面试官可能追问