[백준,c++] 21278번 - 호석이 두 마리 치킨

문제

21278번: 호석이 두 마리 치킨

 

코드

#include <iostream>
#define INF 1e9
using namespace std;


int N, M;
int d[101][101];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i=0; i<101; i++){
        for(int k=0; k<101; k++){
            if(i==k) d[i][k] = 0;
            else d[i][k] = INF;
        }
    }
    cin>>N>>M;
    
    for(int i=0; i<M; i++){
        int a, b; cin>>a>>b;
        d[a][b] = 1;
        d[b][a] = 1;
    }
    
    for(int k=1; k<=N; k++){
        for(int a=1; a<=N; a++){
            for(int b=1; b<=N; b++){
                d[a][b] = min(d[a][b], d[a][k] + d[k][b]);
            }
        }
    }
    
    int chick1 = 0, chick2 = 0;
    int min_d = 1e9;
    
    for(int i=1; i<=N; i++){    // 치킨집 고르기
        for(int j=i+1; j<=N; j++){
            int temp_d = 0;
            for(int k = 1; k<=N; k++){
                temp_d += min(i==k?0:d[i][k], j==k?0:d[j][k]);    // 치킨집까지의 거리 갱신
            }
            if(temp_d < min_d){
                min_d = temp_d;
                chick1 = i;
                chick2 = j;
            }
        }
    }
    
    cout<< chick1 << ' ' << chick2 << ' ' << min_d * 2;
}

 

풀이

플로이드-와샬을통해서 먼저 각각의 노드까지의 최단거리를 전부 갱신시켜줍니다.

그 후, 치킨집을 두 가지 골라야 하기 때문에 for문을 돌려서 두 개의 치킨집 노드를 고르고, 모든 각 노드에서 두 치킨집 사이의 거리가 짧은 것의 거리를 더했을 때, 가장 최소의 거리를 가지는 값을 찾아 치킨집의 노드와 거리의 합을 갱신시켜줍니다.

시간 복잡도는 O(N^3), O(100^3) 이므로 O(10,000,000) 안에 해결이 가능합니다.