백준 1956

문제

---

Floyd-Warshall 알고리즘 사용

간선이 양방향일 수 있다.

또, INF 값이 크기 때문에 2번 더하면 int 범위 상 음수되어버림

예외처리 필요 (거리가 INF인 간선일 때는 최단거리 갱신하지 않도록)

처음에는 dist[i][i]에 0을 저장한 뒤 나머지 dist의 요소를 Floyd-Warshall로 모두 구하고

i번째 노드를 시작과 끝으로 하는 사이클의 최단 거리를 dist[i][i]에 저장

---

Code

package test;

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

public class P1956 {

	static final int INF = 10000 * 400 * (400 - 1) + 1;
	static int[][] dist;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());

		dist = new int[V + 1][V + 1];
		/* 
		 dist 초기화
		 일단 자신에서 자신으로 가는 거리는 0이라고 가정
		 */
		for(int i = 1; i <= V; i++) {
			for(int j = 1; j <= V; j++) {

				dist[i][j] = (i == j ? 0 : INF); 
			}
		}
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			dist[a][b] = c;
		}

		floydWarshallForCycle(V);
		int min = Integer.MAX_VALUE;
		for(int i = 1; i <= V; i++) {
			if(dist[i][i] < INF) {
				min = Math.min(min, dist[i][i]);
			}
		}

		bw.write(String.valueOf(min != Integer.MAX_VALUE ? min : -1)); 

		br.close();
		bw.flush();
		bw.close();
	}
	// int V : 전체 노드(정점) 개수
	private static void floydWarshallForCycle(int V) {
		/*
			Round k : 
			k번 노드를 경로의 중간 지점이라 할 때
			i번 노드부터 j번 노드까지 거리가 짧아지면
			최단 거리 갱신   
		 */
		for(int k = 1; k <= V; k++) {
			for(int i = 1; i <= V; i++) {
				if(dist[i][k] == INF) {
					continue;
				}
				for(int j = 1; j <= V; j++) {
					if(dist[k][j] == INF) {
						continue;
					}

					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}

		/* 
		 사이클 찾기
		 Round i :
		 i번째 노드에서 j번째 노드까지 간 후
		 다시 i번재 노드까지 오는 사이클의 최단 거리
		 */
		for(int i = 1; i <= V; i++) {
			dist[i][i] = INF;

			for(int j = 1; j <= V; j++) {
				if(i == j) {
					continue;
				}
				if(dist[i][j] != INF && dist[j][i] != INF) {
					dist[i][i] = Math.min(dist[i][i], dist[i][j] + dist[j][i]);
				}
			}
		}
	}
}