[JAVA] 백준 11404번- 플로이드

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

11404번: 플로이드

 

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

public class Main{
    public static final int INF = 100000000;
    public static int n, m;
    public static int[][] map;

    public static void floyd(){
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    map[i][j] = Math.min(map[i][j], map[i][k]+map[k][j]); // i->k->j 거리와 i->j 거리 비교
                }
            }
        }
    }
    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()); // 버스의 개수

        map = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) continue; // 출발 도시와 도착 도시가 같으면 0
                map[i][j] = INF;
            }
        }

        while(m-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map[start][end] = Math.min(map[start][end], cost); // 노선이 하나가 아닐 수 있으므로 최솟값으로 갱신
        }

        floyd();

        StringBuilder sb = new StringBuilder();

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(map[i][j] >= INF) sb.append("0 ");
                else sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}