백준 1956번 운동

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

1956번: 운동

플로이드 와샬 연습용문제. 

1. 400 x 400 이므로 인접행렬로 풀었음 (생각해보니 플로이드문제중에 인접리스트로 푸는게 있던가?..)
2. 배열 INF값으로 초기화
3. edge 넣어줌 edges[a][b] = dist;  // a -> b는 거리가 dist
4. 플로이드와샬 경출도 (경유지, 출발지, 도착지)   edges[a][b] > edges[a][k] + edges[k][a] 면 갱신. 출발지에서 어디경유해서 도착지로 가는 비용이 현재 출발지에서 도착지로 최소 비용보다 적은 경우!
5. 사이클이랬으니 출발지 -> 출발지로 가는 최소 비용 체크

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

public class bj1956 {
	static int [][] edges;
	static int V,E;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		edges = new int[V+1][V+1];
		for(int[] e : edges) {
			Arrays.fill(e, 987654321); //INF로 초기화
		}
		for(int e=0;e<E;e++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			edges[a][b] = dist;
		}
		//플로이드와샬 경출도
		for(int k=1;k<V+1;k++) {
			for(int i=1;i<V+1;i++) {
				for(int j=1;j<V+1;j++) {
					edges[i][j] = Math.min(edges[i][k]+edges[k][j],edges[i][j]);
				}
			}
		}
		int min = 987654321;
		for(int i=1;i<=V;i++) {//사이클 최소비용 체크
			min = Math.min(min, edges[i][i]);
		}
		if(min==987654321) min = -1; //사이클이 없음
		System.out.println(min);
	}
}