https://www.acmicpc.net/problem/11404
플로이드 워셜 알고리즘을 사용하여 쉽게 풀 수 있는 문제였다.
다만, 입력값 중 동일 경로에 다른 비용이 존재하는 점, INF 값을 너무 크게 할 경우 오버플로우가 날 수 있다는 점과 적을 경우 값이 적용되지 않는다는 점을 유의하도록 하자.
public class BOJ_11404_플로이드 {
static final int INF = Integer.MAX_VALUE / 2 - 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int map[][] = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(map[i], INF);
}
//값 채우기
while(M-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()) - 1;
int end = Integer.parseInt(st.nextToken()) - 1;
int cost = Integer.parseInt(st.nextToken());
map[start][end] = Math.min(map[start][end], cost);
}
//계산
for (int k = 0; k < N; k++) { //경유지
for (int i = 0; i < N; i++) { //출발
if(i == k) continue; //출발지와 경유지가 같다면 스킵
for (int j = 0; j < N; j++) { //도착지
if(i == j || k == j) continue; //출발지와 도착지, 혹은 경유지와 도착지가 같을 수 없음
map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);
}
}
}
//출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j] == INF) bw.write("0 ");
else bw.write(map[i][j] + " ");
}
bw.write("\n");
}
bw.close();
}
}