11404. 플로이드 (Java)

이름에서 알수 있듯이 위 문제는 플로이드 워셜 의 알고리즘을 사용한다.

플로이드 워셜의 특징으로는

모든간선의 모든정점to 모든정점의 최소 거리를 체크한다.

음의 간선 사용 가능

3중 for문을 돈다

사용해본 결과 foreach 문 을 쓸게 아니라면 

아무래도 인접행렬 을 사용하는게 편해보임 but 시간이 좀 걸려보임

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

public class Main {

	static int N, M;
	static int[][] bus;
	static int[][] Graph;
	static int INF = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		Graph = new int[N+1][N+1];
		bus = new int[M][3];
		
		for(int i = 0 ; i <= N ; i++) {
			for(int j = 0 ; j <= N ; j++) {
				Graph[i][j] = INF;
				if(i == j)
					Graph[i][j] = 0;
			}
		}
		
		for(int i = 0 ; i < M ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			bus[i][0] = Integer.parseInt(st.nextToken());
			bus[i][1] = Integer.parseInt(st.nextToken());
			bus[i][2] = Integer.parseInt(st.nextToken());
			if(Graph[bus[i][0]][bus[i][1]]>bus[i][2])
			Graph[bus[i][0]][bus[i][1]] =bus[i][2];
		}
		for(int k = 0 ; k < N + 1 ; k++) {	
			for(int i = 0 ; i < N + 1 ; i++) {		
				for(int j = 0 ; j < N + 1 ; j++) {	
					if(Graph[i][k] != INF && Graph[k][j] != INF)
						Graph[i][j] = Math.min(Graph[i][j],Graph[i][k]+Graph[k][j]);
				}
			}
		}
		for(int i = 1 ; i <= N ; i++) {
			for(int j = 1 ; j <= N ; j++) {
				if(Graph[i][j]==INF)
					System.out.print(0+" ");
				else	
					System.out.print(Graph[i][j]+" ");
			}
			System.out.println();
		}
	}
}