[BaekJoon] 백준 11404번: 플로이드

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

11404번: 플로이드

 

 

플로이드 와샬 알고리즘을 구현하는 문제이다. 

 

전체 코드 > 

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

public class Main {
    static int[][] city;
    static int M;
    static int N;
    
    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());
    
        city = new int[N+1][N+1];
        
        for(int i = 1; i<=N; i++) {
            for(int j = 1; j<=N; j++) {
                if (i == j) {
                    city[i][j] = 0;
                } else {
                    city[i][j] = 99999999;
                }
            }
        }
        
        for(int i = 0; i<M; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int c = Integer.parseInt(input[2]);
            
            city[a][b] = Math.min(city[a][b], c);
        }
        
        for(int i = 1; i<=N; i++) {
            for(int j = 1; j<=N; j++) {
                for(int k = 1; k<=N; k++) {
                    if (j != k) {
                        city[j][k] = Math.min(city[j][i] + city[i][k], city[j][k]);
                    }
                }
            }
        }
        
        for(int i = 1; i<=N; i++) {
            for(int j = 1; j<=N; j++) {
                if (city[i][j] >= 99999999) {
                    System.out.print("0");
                } else {
                    System.out.print(city[i][j]);
                }
                
                if (j != N) {
                    System.out.print(" ");
                }
            }
            System.out.println("");
        }
        
    }
}