[백준:11404 / JAVA] 플로이드

---

풀이

출발 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수도 있다. 이말은 즉슨

만약 1 4 1과 1 4 2 가 입력으로 들어오면 1 4 1 가 입력이 되야한다.

문제도 플로이드이기 때문에 플로이드 와샬 알고리즘을 고대로 사용

---

package 플로이드;

import java.util.*;

public class Main {

	public static final int INF = (int)1e9;
	//도시 : 노드의 개수 (N)
	//버스 : 간선의 개수 (M)
	public static int n, m;
	
	public static int[][] graph = new int[101][101];
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		m = scan.nextInt();
		
		//최단 거리 테이블 초기화
		for(int i = 0; i < 101; i++) {
			Arrays.fill(graph[i], INF);
		}
		
		//자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
		for(int a = 1; a <= n; a++) {
			for(int b = 1; b <= n; b++) {
				if(a == b) graph[a][b] = 0;
			}
		}
		
		for(int i = 0; i < m; i++) {
			//a에서 b로 가는 비용은 c
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			
			//출발 도시와 도착 도시가 같지만 시간이 다른 입력값이 들어올 수 있음
			//예를 들어 "1 4 1"과 "1 4 2"가 입력으로 들어오면, "1 4 1"을 택해야함
			graph[a][b] = Math.min(graph[a][b], c);
		}
		//각 간선에 대한 정보를 입력받아, 그 값으로 초기화
		for(int k = 1; k <= n; k++) {
			for(int a = 1; a <= n; a++) {
				for(int b = 1; b <= n; b++) {
					graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
				}
			}
		}
		for(int a = 1; a <= n; a++) {
			for(int b = 1; b <= n; b++) {
				if(graph[a][b] == INF) {
					System.out.print(0 + " ");
				}
				else {
					System.out.print(graph[a][b] + " ");
				}
			}
			System.out.println();
		}
		scan.close();
	}
}