백준 13424(비밀 모임)

www.acmicpc.net/problem/13424

13424번: 비밀 모임

 

그래프로 최단 거리를 구하는 문제이다. 

 

최단 거리 알고리즘은 대표적으로 다익스트라가 있는데 이 알고리즘은 1vsN이므로 이 문제에서 요구하는 NvsN과는 좀 맞지 않는다

 

그래서 NvsN의 최단거리 알고리즘인 플로이드 와샬을 사용한다. 

 

그래프를 구현하고, 플로이드 와샬 이용, 원하는 값을 구한다. 

 

주의해야 할 점은 본인과 본인의 거리는 0이다 

#include<iostream>
#include<vector>
using namespace std;
#define MAX 105

int N, M, INF=987654321;
int T, K;

int main() {
	cin >> T;
	while (T--) {
		int dist[MAX][MAX];
		vector<int> v;
		cin >> N >> M;

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j) {
					dist[i][j] = 0;
					continue;
				}
				dist[i][j] = INF;
			}
		}
		for (int i = 0; i < M; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			dist[a][b] = c;
			dist[b][a] = c;
		}
		cin >> K;
		for (int i = 0; i < K; i++) {
			int a;
			cin >> a;
			v.push_back(a);
		}

		for (int l = 1; l <= N; l++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (dist[i][l] + dist[l][j] < dist[i][j])
						dist[i][j] = dist[i][l] + dist[l][j];
				}
			}
		}

		int min_n = INF;
		int idx;
		for (int i = 1; i <= N; i++) {
			int sum = 0;
			for (int j = 0; j < v.size(); j++) {
				sum += dist[i][v[j]];
			}
			if (sum < min_n) {
				min_n = sum;
				idx = i;
			}
		}
		cout << idx << '\n';
	}
}