LC.P1334[阈值距离内邻居最少的城市]

方法一：Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {

    private static final int INF = 0x3f3f3f3f;
    int[][] g;
    int n;
    int[] dist;
    boolean[] visited;
    int distanceThreshold;

    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        g = new int[n][n];
        this.n = n;
        dist = new int[n];
        visited = new boolean[n];
        this.distanceThreshold = distanceThreshold;
        for (int[] e : g) Arrays.fill(e, INF);
        for (int[] e : edges) {
            int a = e[0], b = e[1], w = e[2];
            g[a][b] = w;
            g[b][a] = w;
        }
        int ans = n, cnt = INF;
        for (int i = n - 1; i >= 0; --i) {
            int t = dijkstra(i);
            if (t < cnt) {
                cnt = t;
                ans = i;
            }
        }
        return ans;
    }

    private int dijkstra(int u) {
        Arrays.fill(dist, INF);
        Arrays.fill(visited, false);
        dist[u] = 0;
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (k == -1 || dist[k] > dist[j])) {
                    k = j;
                }
            }
            visited[k] = true;
            for (int j = 0; j < n; ++j) {
                dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
            }
        }
        int cnt = 0;
        for (int d : dist) {
            if (d <= distanceThreshold) ++cnt;
        }
        return cnt;
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^2)$

方法二：Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

    private static final int INF = 0x3f3f3f3f;

    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] g = new int[n][n];
        for (int[] e : g) Arrays.fill(e, INF);
        for (int[] e : edges) {
            int a = e[0], b = e[1], w = e[2];
            g[a][b] = w;
            g[b][a] = w;
        }
        for (int k = 0; k < n; ++k) {
            g[k][k] = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
        int ans = n, cnt = INF;
        for (int i = n - 1; i >= 0; --i) {
            int t = 0;
            for (int d : g[i]) {
                if (d <= distanceThreshold) {
                    ++t;
                }
            }
            if (t < cnt) {
                cnt = t;
                ans = i;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^2)$