[백준 21940] 가운데에서 만나기 (C++)

이 문제는 친구들의 왕복시간들 중 최대가 최소가 되는 도시 $X$를 선택하는 문제이다.

따라서, 왕복시간을 구하기 위해, 도시간 이동 시간(비용)을 구해야 하는데, 일반적으로 최소 비용이 이동 비용이 된다. 수학에서 거리를 규정하는 것과 같은 맥락이라 보면 된다. 즉, 이동 시간도 여러 개가 나올 수 있기 때문에, 그 중 최소를 이동 시간으로 정의된 것 같다.

이제, 왕복시간을 통해 도시 $X$를 선택해야 한다. 문제의 요구조건대로, 먼저 임의의 도시 $X$로의 친구들의 왕복시간들 중 최대인 것을 저장한 뒤, 이 값들 중 최소값인 도시들을 구하면 된다.

요약해보자면, 각 도시에서 가장 먼 친구를 기준으로, 왕복시간이 가장 적은 도시에서 만나는 상황임을 알 수 있다.

시간복잡도는 입력이 $O(N + M + K)$ 플로이드 워셜 알고리즘이 $O(N^3)$이고, 왕복시간 구하기가 $O(NK)$, 최소값인 도시 구하기가 $O(N)$이므로 전체 시간 복잡도는 $O(N^3)$이 되어, 시간 내에 답을 구할 수 있다.

이를 코드로 옮겨보면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 10'000;
int n, m, k;
int w[201][201], t[201], city[201];

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

	// 입력
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		fill(w[i], w[i] + n + 1, INF);
		w[i][i] = 0;
	}
	for (int i = 0, a, b, c; i < m; i++) {
		cin >> a >> b >> c;
		w[a][b] = min(w[a][b], c);
	}
	cin >> k;
	for (int i = 1; i <= k; i++) cin >> city[i];

	// 플로이드로 이동시간
	for (int v = 1; v <= n; v++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				w[i][j] = min(w[i][j], w[i][v] + w[v][j]);
			}
		}
	}

	// 임의의 도시로의 왕복시간 구하기 (최대값 저장)
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			t[i] = max(t[i], w[i][city[j]] + w[city[j]][i]);
		}
	}

	// 왕복시간들 중 최소인 도시 구하기
	int mn = *min_element(t + 1, t + n + 1);
	for (int i = 1; i <= n; i++) {
		if (t[i] == mn) cout << i << " ";
	}
}