<백준> 11404번 자바 알고리즘

import java.util.Scanner;



class Main {

  private static int a;
  private static int b;
  private static int c;
  private static int n;
  private static int m;
  static int[][] d;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    d = new int[n][n];
    // 5, 14 받음
    for(int i=0; i < n; i++){
      for (int j=0; j < n; j++){
        if(i == j){ d[i][j] = 0;}
        else{
          d[i][j] = 1000000000;
        }
      }
    }
    for(int i=0; i < m; i++){
      a = sc.nextInt() - 1;
      b = sc.nextInt() - 1;
      c = sc.nextInt();
      // 왜 min을 사용 해야 되나? => 1 4 1 , 1 4 2 같이 중복되서 입력 가능해서 
      d[a][b] = Math.min(d[a][b], c);
    }
    // 초기화 완료 
    
    floyd();

    for(int i=0; i < n; i++){
      for(int j=0; j < n; j++){
        if(d[i][j] >= 1000000000){
          System.out.print(0 + " ");
        }else{
        System.out.print(d[i][j] + " ");
        }
      }
      System.out.println();
    }
  }
  static void floyd() {
    for(int k = 0; k < n; k++){
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
        }
      }
    }
  }
}

 

플로이드 와샬 알고리즘 개념 문제이다