061 : 가장 빠른 버스 노선 구하기

 

 

에지 거리 값을 넣기 전에, 에지가 없을 수도 있으므로 초기화를 해준다

 

-

 

모든 노드와 노드 사이를 출력해야 하므로

 

 

 

 

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();

        // TP
        int[][] TP = new int[V+1][V+1];
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i == j)
                    TP[i][j] = 0;
                else
                    TP[i][j] = Integer.MAX_VALUE;
            }
        }

        // D2TP
        for (int i = 1; i <= E; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int w = sc.nextInt();
            if (TP[s][e] > w)
                TP[s][e] = w;
        }

        // OP
        for (int k = 1; k <= V; k++) {
            for (int i = 1; i <= V; i++) {
                for (int j = 1; j <= V; j++) {
                    if (TP[i][j] > TP[i][k] + TP[k][j])
                        TP[i][j] = TP[i][k] + TP[k][j];
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (TP[i][j] == Integer.MAX_VALUE)
                    System.out.print("0 ");
                else
                    System.out.print(TP[i][j] + " ");
            }
            System.out.println();
        }
    }
}