[백준][Java] 11404번 플로이드 (floyd warshall, DP)

[백준][Java] 11404번 플로이드 (floyd warshall, DP)

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.StringTokenizer;

public class Main {

private static BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));

private static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System . out ));

static int [][] Dist;

static int INF = 100000 * 200 ;

static void floyd( int n) {

for ( int k = 0 ; k < n; k + + ) {

for ( int i = 0 ; i < n; i + + ) {

for ( int j = 0 ; j < n; j + + ) {

if (Dist[i][k] + Dist[k][j] < Dist[i][j]){

Dist[i][j] = Dist[i][k] + Dist[k][j];

}

}

}

}

}

public static void main( String [] args) throws IOException{

int n = Integer. parseInt (br.readLine());

int m = Integer. parseInt (br.readLine());

Dist = new int [n][n];

for ( int i = 0 ; i < n; i + + ) {

for ( int j = 0 ; j < n; j + + ) {

if (i = = j) Dist[i][j] = 0 ;

else Dist[i][j] = INF;

}

}

for ( int i = 0 ; i < m; i + + ) {

StringTokenizer stk = new StringTokenizer(br.readLine(), " " );

int a = Integer. parseInt (stk.nextToken()) - 1 ;

int b = Integer. parseInt (stk.nextToken()) - 1 ;

int c = Integer. parseInt (stk.nextToken());

Dist[a][b] = Math.min(Dist[a][b],c);

}

floyd(n);

for ( int i = 0 ; i < n; i + + ) {

for ( int j = 0 ; j < n; j + + ) {

if (Dist[i][j] = = INF) Dist[i][j] = 0 ;

}

}

for ( int i = 0 ; i < n; i + + ) {

for ( int j = 0 ; j < n; j + + ) {

bw.write( String . valueOf (Dist[i][j]));

if (j < n - 1 ) bw.write( " " );

}

bw.write( "

" );

}

bw.flush();

bw.close();

}

}

from http://aig2029.tistory.com/260 by ccl(A) rewrite - 2021-09-08 05:00:42