[백준] 1956번:운동 (Java 자바)

문제

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

1956번: 운동

 

 

풀이 및 소스코드

 

플로이드 와샬 알고리즘으로 푸는 문제이다.

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

class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());

		int[][] dp = new int[v][v];
		for (int i = 0; i < v; i++) {
			Arrays.fill(dp[i], 10001);
		}

		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken());
			dp[a][b] = c;
		}
		
		for (int k = 0; k < v; k++) {
			for (int i = 0; i < v; i++) {
				for (int j = 0; j < v; j++) {
					dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
				}
			}
		}
		int res = Integer.MAX_VALUE;

		for (int i = 0; i < v; i++) {
			if (res > dp[i][i]) {
				res = dp[i][i];

			}
		}

		if (res == 10001) {
			System.out.println("-1");
		} else {
			System.out.println(res);
		}
	}

}