[자바] 백준 1956 - 운동

시작점과 도착점이 정해져 있지 않고, 경로의 합이 가장 작은 사이클을 찾으면 된다. 

사이클을 어떻게 찾아낼지에 대해 어렵게 생각했는데, 플로이드 워셜 알고리즘 이용해서 dist[1][1], dist[2][2], ..., dist[V][V]의 값들을 확인하면 되는 문제였다. 

 

도시의 개수는 최대 400개이고, 간선의 개수도 최대 V(V-1)라고 했으니 최대 16만개로 보면 된다. 

최대값들을 기준으로 생각했을 때, 간선은 16만번을 읽으면 되고, 플로이드 워셜 알고리즘은 400 x 400 x 400이니까 6천 4백만 정도의 연산만 필요하다. 

 

이 문제가 플로이드 워셜을 이용하면 된다는 걸 알고 나면 엄청 쉬운데, 그걸 알아챌 짬이 부족하다

/* 2020.12.24(목) */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static int MAX = 2000000000; 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().trim().split(" ");
		
		int V = Integer.parseInt(str[0]);
		int E = Integer.parseInt(str[1]);
		
		int[][] dist = new int[V+1][V+1];
		
		for(int i=1;i<=V;i++) {
			Arrays.fill(dist[i], MAX);
		}
		
		
		int s,e,d;
		for(int i=0;i<E;i++) {
			str = br.readLine().trim().split(" ");
			s = Integer.parseInt(str[0]);
			e = Integer.parseInt(str[1]);
			d = Integer.parseInt(str[2]);
			
			dist[s][e] = d;
		}
		
		//플로이드 워셜 
		// k = 경유지
		for(int k=1;k<=V;k++) {
			for(int a=1;a<=V;a++) {
				if(dist[a][k]== MAX) continue;
				for(int b=1;b<=V;b++) {
					if(dist[k][b]== MAX) continue;
					dist[a][b] = Math.min(dist[a][b], dist[a][k]+dist[k][b]);
				}
			}
		}
		
		int result = MAX;
		for(int a=1;a<=V;a++) {
			result = Math.min(result, dist[a][a]); 
		}
		
		if(result == MAX) System.out.println(-1);
		else System.out.println(result);
	}
}