[21278 호석이 두 마리 치킨]

• 문제

https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

 

• 접근 및 해결

1. 각 정점에 대해서 나머지 정점들까지의 최소 거리를 구한다. (플로이드-워샬)
2. 최대 100개의 정점이므로 3중 for문을 사용해 각 정점(집)에서 선택된 치킨 집 2개와의 최소 거리를 구한다.
3. 2에서 최소 값을 구하면 정답!

#include <iostream>
#define INF 987654321;
using namespace std;

int N, M;
int graph[101][101];
int dist[101][101];

int main()
{
    ios_base ::sync_with_stdio(false);
    
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    
    int src, des;
    for(int iter = 0; iter < M; iter++) {
        cin >> src >> des;

        graph[src][des] = graph[des][src] = 1;
    }

    for(src = 1; src <= N; src++) {
        for(des = 1; des <= N; des++) {
            if(src == des) continue;
            
            if(graph[src][des]) {
                dist[src][des] = graph[src][des];
            }
            else {
                dist[src][des] = INF;
            }
        }
    }

    for(int mid = 1; mid <= N; mid++) {
        for(src = 1; src <= N; src++) {
            for(des = 1; des <= N; des++) {
                dist[src][des] = min(dist[src][des], dist[src][mid] + dist[mid][des]);
            }
        }
    }

    int answer = INF;
    pair<int, int> position;

    for(int first = 1; first <= N; first++) {
        for(int second = 1 + 1; second <= N; second++) {
            int total = 0;
            for(int index = 1; index <= N; index++) {
                total += min(dist[first][index], dist[second][index]);
            }

            if(answer > total) {
                answer = total;
                position = make_pair(first, second);
            }
        }
    }

    cout << position.first << " " << position.second << " " << answer * 2 << endl;

    return 0;
}