[백준] 13424 비밀 모임 [JAVA]

문제링크 : www.acmicpc.net/problem/13424

13424번: 비밀 모임

플로이드 워셜로 모든 거리정보를 구한 후 모든 거점에 대해서 비용을 모두 구해보고 가장 작은 거리인 거점을 출력한다

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc= Integer.parseInt(br.readLine());
		for(int a=0;a<tc;a++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int dist[][] = new int[N+1][N+1];
			for(int i=1;i<=N;i++){
				for(int j=1;j<=N;j++){
					if(i==j)dist[i][j] = 0;
					else dist[i][j] = 1000000;
				}
			}
			for(int i=0;i<M;i++){
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				dist[s][e] = c;
				dist[e][s] = c;
			}
			for(int i=1;i<=N;i++){
				for(int j=1;j<=N;j++){
					for(int k=1;k<=N;k++){
						dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
					}
				}
			}
			int person = Integer.parseInt(br.readLine());
			int personInfo[] = new int[person];
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<person;i++){
				personInfo[i] = Integer.parseInt(st.nextToken());
			}
			int ansLen = 10000000;
			int ans = -1;
			for(int i=1;i<=N;i++){
				int tempLen = 0;
				for(int j=0;j<person;j++){
					tempLen += dist[personInfo[j]][i];
				}
				if(tempLen < ansLen){
					ansLen = tempLen;
					ans = i;
				}
			}
			System.out.println(ans);
		}
	}

}