1334. Find the city with the smallest number of neighbors at a threshold distance

//1334. Find the city with the smallest number of neighbors at a threshold distance

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++) {
                if(i == j) {
                    dist[i][j] = 0;
                }
                else {
                    dist[i][j] = Integer.MAX_VALUE / 2;
                }
            }
        }
        
        for(int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int wt = edge[2];
            dist[u][v] = wt;
            dist[v][u] = wt;
        }
        
        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 city = -1;
        int minCount = n;
        
        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;
                city = i;
            }
            else if (count == minCount && i > city) {
                city = i;
            }
        }
        
        return city;
    }
}