LeetCode Daily: Find the City With the Smallest Number of Neighbors at a Threshold.. | July 26, 2024

class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
//Use a large value to represent inifinity
int INF = 10001;
int[][] dist = new int[n][n];

//Initialize distance matrix
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] = INF;
}
}

//Fill initial distances based on edges
for(int[] edge : edges) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
dist[from][to] = weight;
//Since the grapgh is bidirectional
dist[to][from] = weight;
}

//Floyd-Warshall to find the shortest paths bet all pairs
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];
}
}
}

//Determine the city with the smallest nu,ber of reachable cities
int minReachableCities = n;
int bestCity = -1;

for(int i = 0; i < n; i++) {
int reachableCities = 0;
for(int j = 0; j < n; j++) {
if(i != j && dist[i][j] <= distanceThreshold)
reachableCities++;
}
if(reachableCities <= minReachableCities) {
minReachableCities = reachableCities;
bestCity = i;
}
}
return bestCity;

}
}