[Java] 백준 11404번 플로이드 - 플로이드-워셜 알고리즘

문제 이름부터 제발 플로이드-워셜 써달라고 하는 문제

각 정점을 mid로 잡아

W(a,mid) + W(mid,b) 와 W(a,b)를 비교한다.

package class4;

import java.util.*;
import java.io.*;

public class g4_11404{
    static int n, m;
    static int INF = Integer.MAX_VALUE / 2;
    static int[][] table;
    public static void main(String[] args){
        FastScanner fs = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        n = fs.nextInt();
        m = fs.nextInt();
        table = new int[n][n];
        for (int[] ary : table) Arrays.fill(ary, INF);
        for (int i=0;i<m;i++){
            int a = fs.nextInt() - 1, b = fs.nextInt() - 1, w = fs.nextInt();
            if (table[a][b] != INF) w = Math.min(w, table[a][b]);
            table[a][b] = w;
        }
        for (int i=0;i<n;i++) table[i][i] = 0;

        floyd();

        for (int[] ary : table){
            for (int e : ary){
                if (e < INF) pw.printf("%d ", e);
                else pw.printf("%d ", 0);
            }
            pw.println("");
        }

        pw.close();
    }

    static void floyd(){
        for (int mid=0;mid<n;mid++){
            for (int i=0;i<n;i++){
                for (int j=0;j<n;j++){
                    table[i][j] = Math.min(table[i][j], table[i][mid] + table[mid][j]);
                }
            }
        }
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }
    }
}