[SWEA] 4066 All Pair Shortest Path

출처: [SWEA] SW 문제해결 심화 - 동적 계획법

 Input 

1

3 3

1 2 1

2 3 2

3 1 3

 

 Output 

#1 0 1 3 5 0 2 3 4 0

모든 정점에 대해 최단 거리 비용을 구해야 하므로

플로이드 와샬 (Floyd Warshall)을 이용합니다.

플로이드 와샬 (Floyd Warshall)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    public static final int INF = 1000000;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int T = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=T; tc++) {
            st = new StringTokenizer(br.readLine());
             
            int N = Integer.parseInt(st.nextToken());
            // dist 테이블 초기화
            int[][] dist = new int[N + 1][N + 1];
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(i != j) dist[i][j] = INF; 
                }
            }
             
            int M = Integer.parseInt(st.nextToken());
            while (M-- > 0) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                dist[u][v] = Math.min(dist[u][v], cost);
            }
             
            // 중간에 거쳐가는 정점 (k)
            for(int k = 1; k <= N; k++) {
                // 출발 정점 (i)
                for(int i=1; i <= N; i++) {
                    // 도착 정점 (j)
                    for(int j=1; j <= N; j++) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
             
            System.out.print("#" + tc + " ");
            for(int i=1; i <= N; i++) {
                for(int j=1; j <= N; j++) {
                    if(i == j) {
                        System.out.print("0 ");
                    }
                    else if(dist[i][j] >= INF) {
                        System.out.print("-1 ");
                    }
                    else {
                        System.out.print(dist[i][j] + " ");
                    }
                }
            }
            System.out.println();
        }
    }
}