[백준 BOJ][JAVA] 1956번: 운동

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

1956번: 운동

 

 

문제 풀이(코드)

import java.util.*;

public class Main {
	static int[][] graph;
	static int v, e, min = Integer.MAX_VALUE;
	static final int INF = (int)1e9;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		v = scan.nextInt();
		e= scan.nextInt();
		
		graph = new int[v+1][v+1];
		
		for(int i = 0; i <= v; i++)
			Arrays.fill(graph[i],INF);
		
		for(int i = 0; i < e; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			
			graph[a][b] = Math.min(graph[a][b], c);
		}
		
		for(int k = 1; k <= v; k++)
			for(int i = 1; i <= v; i++)
				for(int j = 1; j <= v; j++)
					graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
		
		for(int i = 1; i <= v; i++)
			min = Math.min(min, graph[i][i]);
		
		if(min == INF)
			System.out.println(-1);
		else
			System.out.println(min);
		
		scan.close();
	}

}