Find the City With the Smallest Number of Neighbors at a Threshold Distance LeetCode solution in Java

1
class Solution {
2
  public int findTheCity(int n, int[][] edges, int distanceThreshold) {
3
    int[][] graph = new int[n][n];
4
    for (int[] row : graph) Arrays.fill(row, Integer.MAX_VALUE);
5

6
    for (int i = 0; i < n; i++) graph[i][i] = 0;
7

8
    for (int[] edge : edges) {
9
      graph[edge[0]][edge[1]] = edge[2];
10
      graph[edge[1]][edge[0]] = edge[2];
11
    }
12

13
    for (int k = 0; k < n; k++) {
14
      for (int i = 0; i < n; i++) {
15
        for (int j = 0; j < n; j++) {
16
          if (graph[i][k] != Integer.MAX_VALUE && graph[k][j] != Integer.MAX_VALUE) {
17
            if (graph[i][k] + graph[k][j] < graph[i][j]) graph[i][j] = graph[i][k] + graph[k][j];
18
          }
19
        }
20
      }
21
    }
22

23
    int ans = 0;
24
    int city = Integer.MAX_VALUE;
25
    ;
26

27
    for (int i = 0; i < n; i++) {
28
      int current = 0;
29
      for (int j = 0; j < n; j++) {
30
        if (i != j && graph[i][j] <= distanceThreshold) current++;
31
      }
32
      if (current <= city) {
33
        ans = i;
34
        city = current;
35
      }
36
    }
37

38
    return ans;
39
  }
40
}