백준_11404_플로이드 (플로이드-워셜 알고리즘)

for문 3개를 이용하여 푸는 그래프 관련 문제로 

graph[시작][끝] = Math.min(graph[시작][끝], graph[시작][경유]+[경유][끝])이 핵심이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class boj_11404_플로이드 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][N];
        st = new StringTokenizer(br.readLine());
        int B = Integer.parseInt(st.nextToken());
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] = 10000000;
            }
        }
        for (int i = 0; i < B; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            map[start - 1][end - 1] = Math.min(map[start - 1][end - 1], value);
        }
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);
                }
            }
        }
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 10000000 || i == j) {
                    System.out.print(0 + " ");
                } else
                    System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}