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

📌 문제

BOJ 바로가기

도시와 도시 간의 거리(시간) 정보가 담겨있는 그래프가 주어진다. 각 도시에서 다른 도시로 갈 수 있는 최소 시간을 구한 다음에, 친구들의 최대 왕복 시간이 최소가 되는 도시를 구해야 한다.

🗡 풀이

📍 플로이드-워셜 알고리즘을 이용해 2차원의 최소시간 배열을 만든다.

📍 이후 이중 for문을 사용해 각 도시별 최대 왕복시간을 구한 다음, 우선순위 큐에 넣는다.

우선순위 큐에 {최대 왕복시간, 도시 번호} 쌍을 push 최대 왕복시간이 작은 순서대로 자동적으로 정렬된다.

📍 pq.top().first를 ans_time으로 지정한 다음, pop한다. 이후 while문을 돌리며 pq.top().first의 값이 ans_time과 같은 경우에만 출력을 계속한다.

🚩 소스코드

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, k, ans_time;
	int t[201][201], fr[201];
	cin >> n >> m;
	// 플로이드
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			t[i][j] = i == j ? 0 : INF;
	}
	for (int i = 0; i < m; i++) {
		int from, to, time;
		cin >> from >> to >> time;
		t[from][to] = time;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++)
				t[i][j] = min(t[i][j], t[i][k] + t[k][j]);
		}
	}

	cin >> k;
	for (int i = 1; i <= k; i++)
		cin >> fr[i];

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int mini = 2147483647;
	for (int i = 1; i <= n; i++) {
		int maxi = 0;
		// 최대 왕복시간 구하기
		for (int j = 1; j <= k; j++) {
			if (maxi < t[fr[j]][i] + t[i][fr[j]])
				maxi = t[fr[j]][i] + t[i][fr[j]];
		}
		pq.push({ maxi, i }); // 우선순위 큐에 최대 왕복시간이 작은 순서로 자동 정렬
	}
	// 정답 출력
	cout << pq.top().second << ' ';
	ans_time = pq.top().first;
	pq.pop();
	while (!pq.empty() && pq.top().first == ans_time) {
		cout << pq.top().second << ' ';
		pq.pop();
	}
	return 0;
}