문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.
  • 간선의 비용은 T이다.

  • 모든 정점에서 특정 정점으로 이동할 때 왕복 비용이 최소가 되는 정점의 번호를 출력하라

  • 문제 분류
    • Graph, Floyd


2. 알고리즘 설계

  • 플로이드-워셜 알고리즘 문제이다.
  • 입력받기 전에 자기 자신으로 이동하는 경로의 비용은 0, 나머지는 INF로 채운다.
  • 간선 비용을 입력받을 때, 입력받은 간선의 비용이 더 적을때만 갱신한다.
  • 플로이드 값을 구한다.
  • i 정점에서 모든 정점으로 왕복하는 비용을 구한다.
    • D[i][j] + D[j][i]
  • 비용과 시작 정점 i를 pair 자료형에 저장한다.
  • 비용이 적은 순으로 정렬하고, 정렬된 원소의 첫 번째 원소의 비용과 같은 정점의 번호를 전부 출력한다.


3. 전체 코드

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

const int INF = 0x3f3f3f3f;
int a, b, t, n, m, k, D[202][202];
vector<int> C;
vector<pair<int,int>> res;

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

	cin >> n >> m;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			D[i][j] = (i==j ? 0 : INF);

	while(m--) {
		cin >> a >> b >> t;
		D[a][b] = min(D[a][b], t);
	}
	cin >> k;
	while(k--) {
		cin >> a;
		C.push_back(a);
	}

	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

	for(int i=1; i<=n; i++) {
		int mx = 0;
		for(int j : C)
			mx = max(mx, D[i][j] + D[j][i]);
		res.push_back({mx, i});
	}

	sort(res.begin(), res.end());
	int x = res[0].first;
	for(auto y : res) if(x == y.first) cout << y.second << ' ';

	return 0;
}