[플로이드 워셜] 플로이드(백준 11404번, 자바)

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

11404번: 플로이드

 

 

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

public class Main_11404_플로이드 {

	static int n,m;
	static int[][] map;
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 n = Integer.parseInt(br.readLine());
		 m = Integer.parseInt(br.readLine());
		 
		 map=new int[n+1][n+1];
		 for(int i=0;i<m;i++) {
			 	StringTokenizer st=new StringTokenizer(br.readLine());
				int x=Integer.parseInt(st.nextToken());
				int y=Integer.parseInt(st.nextToken());
				int d=Integer.parseInt(st.nextToken());
				if(map[x][y]==0) map[x][y]=d;
				else if(map[x][y]>d) map[x][y]=d;

		 }
		 
		 for(int k=1;k<=n;k++) {
			 for(int i=1;i<=n;i++) {
				 for(int j=1;j<=n;j++) {
					 	if(i==j) continue; 
					 	if(map[i][k]>0 &&  map[k][j]>0) { //해당 버스가 존재한다면
					 		 if(map[i][j]==0) map[i][j]=map[i][k]+map[k][j];
							 else map[i][j]=Math.min(map[i][k]+map[k][j], map[i][j]);
					 	}
				 }
			 }
		 }
		 
		 for(int i=1;i<=n;i++) {
			 for(int j=1;j<=n;j++) {
				 sb.append(map[i][j]+" ");
			 }sb.append("\n");
		 }
		 System.out.println(sb.toString());
	}

}