백준 1956 운동 (Gold 4)

간선이 양수인 그래프에서 최단 사이클을 찾는 문제 -> 플로이드 워셜
구현도 간단하고 시간도 얼마 안 걸림
걸린시간 20분, 난이도 2.5/10

/*
 * 다익스트라의 경우 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 
 * 그러나 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 플로이드 워셜 알고리즘 이용
 * 이 문제는 싸이클을 구해야하니까 MST (x), n to n 최소거리, 간선은 양수 FW이용
 * 만약에 음수인 간선이 존재했다면 Bellman-Ford를 이용해야함 
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Exercise {
	static int INF = 10000000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());	
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int[][] adj = new int[V+1][V+1];
		
		for(int i = 0; i < V+1; i++) {
			for(int j = 0; j < V+1; j++) {
				adj[i][j] = INF;
			}
		}
		
		//인접리스트 초기화 
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			adj[s][e] = c;
		}
		
		
		//플로이드 워셜
		for(int i = 1; i < V+1; i++) {
			for(int j = 1; j < V+1; j++) {
				for(int k = 1; k < V+1; k++) {
					adj[j][k] = Math.min(adj[j][k],adj[j][i]+adj[i][k]);
				}
			}
		}
		
		//사이클을 찾는 문제이므로 1->1 2->2 ... n -> n인 경우를 찾는다 
		int result = INF;
		for(int i = 1; i < V+1; i++) {
			result = Math.min(result, adj[i][i]);
		}
		
		if(result==INF)System.out.println(-1);
		else System.out.println(result);
	}
}