[백준 알고리즘 C++] 21940번: 가운데에서 만나기

플로이드 알고리즘으로 풀 수 있는 알고리즘이다.

 

전체 노드로부터의 한 노드의 가중치의 합을 구해야 하므로 플로이드 알고리즘을 사용 할 수 있다.

 

기본적인 플로이드 알고리즘 문제이다.
다른 점은 한 노드에서 다른 노드까지의 단방향이지만, 왕복의 가중치를 구해야 하는 점이다.

문제의 해석이 조금 귀찮은 편이다.
친구들의 위치에서의 최소값 중에서 (플로이드로 구한 가중치 값 중에서) 최대값이 가장 작은 노드를 구하는 것이 문제이다.

기본적인 플로이드 알고리즘으로 각 노드의 가중치를 구해 준 다음,

친구들의 위치에 따른 노드의 값을 구해주고 비교해서 최소값을 출력하는데, 여러개 있으면 오름차순으로 출력해야 한다.

 

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

std::vector<std::vector<long long>> city;
std::vector<int> f;
std::vector<long long> list;

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

	int n, m;
	std::cin >> n >> m;

	city.assign(n + 1, std::vector<long long>(n + 1, INT_MAX));

	long long a, b, c;
	for (int i{ 0 }; i < m; i++) {
		std::cin >> a >> b >> c;
		city[a][b] = std::min(city[a][b], c);
	}

	for (int k{ 1 }; k <= n; k++) {
		for (int i{ 1 }; i <= n; i++) {
			for (int j{ 1 }; j <= n; j++) {
				if (i == j) {
					city[i][j] = 0;
					continue;
				}
				city[i][j] = std::min(city[i][j], city[i][k] + city[k][j]);
			}
		}
	}

	int t;
	std::cin >> t;

	f.assign(t + 1, 0);

	for (int i{ 1 }; i <= t; i++) {
		std::cin >> f[i];
	}
	
	long long ans = 0;
	long long res = INT_MAX;

	for (int k{ 1 }; k <= n; k++) {
		for (int i{ 1 }; i <= t; i++) {
			if (city[f[i]][k] != INT_MAX && city[k][f[i]] != INT_MAX) {
				ans = std::max(ans, city[f[i]][k] + city[k][f[i]]);
			}
			else {
				i = t + 1;
				ans = INT_MAX;
			}
		}
		if (ans != INT_MAX) {
			if (res == ans) {
				list.push_back(k);
			}
			else if (res > ans) {
				list.assign(0, 0);
				list.push_back(k);
				res = ans;
			}
		}
		ans = 0;
	}


	for (int i{ 0 }; i < list.size(); i++) {
		std::cout << list[i] << " ";
	}
	std::cout << "\n";
}