[Leetcode,c++] Find the City With the Smallest Number of Neighbors at a Threshold Distance

문제

Find the City With the Smallest Number of Neighbors at a Threshold Distance - LeetCode

 

코드

class Solution {
    int graph[101][101]={0,};
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {


        for (int i = 0; i < 101; i++) {
            fill(graph[i], graph[i] + 101, 1e9);
        }

        for(int i=0; i<n; i++){
            for(int k=0; k<n; k++){
                if(i==k) graph[i][k]=0;
            }
        }

        for(int i=0; i<edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            int cost = edges[i][2];
            graph[a][b] = cost;
            graph[b][a] = cost;
        }


        for(int k=0; k<n; k++){
            for(int a=0; a<n; a++){
                for(int b=0; b<n; b++){
                    graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b]);
                }
            }
        }

        int ans=0,city=1e9;

        for(int i=0; i<n; i++){
            int cnt=0;
            for(int k=0; k<n; k++){
                if(graph[i][k]<=distanceThreshold) cnt++;
            }

            if(city>=cnt){
                ans=i;
                city=cnt;
            }
        }
        return ans;
    }
};

 

풀이

한 도시에서 distanceThreshold의 비용으로 갈 수 있는 모든 도시의 경우의 수가 제일 적은 도시 번호를 출력합니다. 만약 경우의 수가 같은 도시 번호가 여러 개라면 큰 숫자의 도시 번호를 출력합니다.

기본적인 플로이드-와샬 알고리즘을 이용하여 모든 도시경로의 최소비용을 기록한 후, 문제 조건에 맞는 도시 번호를 찾아 출력합니다.