[ boj : 21278 ] 호석이 두 마리 치킨

www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

문제 : n개의 정점과 m개의 간선이 주어집니다. 이때 2개의 정점을 선택하는데 모든 정점에서 선택한 2개의 정점 중 가까운 정점과의 거리가 최소가 되게끔 만드시오

 

해설 : n이 최대 100밖에 안된다는 것은 별짓거리를 다해도 된다는 뜻이죠. 100C2 로 정점을 선택해서 bfs를 돌려도 되고 플로이드-와샬 알고리즘을 사용해서 구해도 되고 등등

 

전 맘편하게 플로이드-와샬 알고리즘을 사용했습니다. 모든 정점과의 거리의 최소값을 구해준 다음에 정점을 선택해야되는데 조건에서 무조건 작은 번호가 우선순위를 가지니 그냥 for문 2개를 돌려서 구해주면 됩니다.

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct info {
	int x, y, dis;
};

int n, m;
int adj[101][101],dist[101][101];
const int INF = (int)1e9;

int solve(int x, int y);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int x, y;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		adj[x][y] = adj[y][x] = 1;
	}

	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			if (i == j)continue;
			else if (adj[i][j])
				dist[i][j] = adj[i][j];
			else
				dist[i][j] = INF;
		}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	int ax,ay,ans = INF;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++){
			int ret = solve(i, j);
			if (ans > ret) {
				ax = i, ay = j;
				ans = ret;
			}
		}
	cout << ax<<" " << ay <<" "<< ans*2;
	return 0;
}
int solve(int x, int y)
{
	int distance = 0;
	for (int i = 1; i <= n; i++)
		distance += min(dist[x][i], dist[y][i]);
	return distance;
}