---
title: 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
tags: graph
description: share source code.
---

# 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

class Solution {
    
    // 每ㄧ個城市能到達的不同城市
    Map<Integer, Set<Integer>> CityReachCities = new HashMap<>();
    
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int [][] dist = new int [n][n];
        for(int i = 0; i < n; i++){
            CityReachCities.put(i, new HashSet<>());
            Arrays.fill(dist[i] , -1);
        }

        for(int i = 0; i < edges.length; i++){
            dist[edges[i][0]][edges[i][1]] = edges[i][2];
            dist[edges[i][1]][edges[i][0]] = edges[i][2];
            
        }
        
        Set<Integer> visited = new HashSet<>();
        
        // 加入每ㄧ個能到達的不同城市
        for(int i = 0; i < n; i++){
            
            visited.add(i);
            dfs(n, dist, i, i, -1, 0, distanceThreshold, visited);
            visited.clear();
        }
        
        // System.out.println("key: " + CityReachCities.keySet().toString());
        // System.out.println("val: " + CityReachCities.values().toString());
        
        // 最大 id 的城市
        int max_city = -1;
        // 最小的鄰居
        int min_num = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            if(min_num >= CityReachCities.get(i).size()){
               min_num = CityReachCities.get(i).size();
               max_city = i; 
              
            }
        }
        
        return max_city;
    }
    
    public void dfs(int n, int [][] dist, int start, int u, int p, int sum, int distanceThreshold, Set<Integer> visited){
        
     
        for(int v = 0; v < n; v++){
            if(v == p ||  dist[u][v] == -1 || sum + dist[u][v] > distanceThreshold || visited.contains(v)){
                continue;
            }
            
            CityReachCities.get(start).add(v); 
           
            visited.add(v);
            dfs(n, dist, start, v, u, sum + dist[u][v], distanceThreshold, visited); 
            visited.remove(visited.size() -1);
        }
        
         
    }
}