[알고리즘] 백준 13424번: 비밀 모임 (C++)

https://www.acmicpc.net/problem/13424

13424번: 비밀 모임

다익스트라로 하기엔 여러 번 함수 콜이 귀찮아서 플로이드로 한 번에 모든 최소 비용 경로를 구했다.

(얼마나 귀찮았으면 플로이드도 짜놓고 콜 안 해서 틀렸을까^^)

 

1) 모든 최소 비용 경로를 구한다.

2) 1~n까지 돌며 방에 있는 사람들로부터 각 노드로 가는 최소 비용을 다 더 했을 때, 제일 작은 방을 출력한다.

 

#include <iostream>
#include <cmath>
#include <vector>
#define MAX 100 + 1
#define INF 987654321
using namespace std;

int T;
int n;
int graph[MAX][MAX];

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}
}

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		int m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) continue;
				graph[i][j] = INF;
			}
		}

		for (int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			if (c < graph[a][b]) { // 잘못된 간선 추가 방지
				graph[a][b] = c;
				graph[b][a] = c;
			}
		}

		floydWarshall();

		int k;
		cin >> k;
		vector<int> friends;
		for (int i = 0; i < k; i++) {
			int room;
			cin >> room;
			friends.push_back(room);
		}

		int minValue = INF;
		int result = -1;
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = 0; j < friends.size(); j++) {
				sum += graph[friends[j]][i];
			}

			if (sum < minValue) {
				minValue = sum;
				result = i;
			}
		}

		cout << result << '\n';
	}
	return 0;
}