백준 1956 : 운동

https://www.acmicpc.net/problem/1956

1956번: 운동

[ 문제풀이 ]

모든 정점에서 모든 정점으로의 최소 경로를 구할 수 있는 플로이드 와샬 알고리즘을 사용하면 쉽게 해결할 수 있다.

dist[i][i]의 값이 INF가 아니라는 것은 자신에게 돌아올 수 있다는 것이기 때문에 i번 정점에서 출발하여 i번 정점으로 돌아오는 사이클 경로가 있다는 것을 의미한다.

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

public class Main {

	static final int INF = 4000001;
	static int V, E;
	static int[][] dist;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			dist = new int[V + 1][V + 1];
			for (int i = 1; i <= V; ++i) Arrays.fill(dist[i], 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;
			}
			
			floydWarshall();

			int cost = INF;
			for (int i = 1; i <= V; ++i) cost = Math.min(cost, dist[i][i]);
			bw.write((cost == INF ? -1 : cost) + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void floydWarshall() {
		for (int k = 1; k <= V; ++k) {
			for (int i = 1; i <= V; ++i) {
				for (int j = 1; j <= V; ++j) {
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}
	}
}