플로이드-워셜 알고리즘

11404 플로이드 : https://www.acmicpc.net/problem/11404

플로이드-워셜 알고리즘

1) D[i][j] : 정점 i에서 j까지의 최단 거리를 저장하는 배열

i==j 이면 D[i][j] = 0

i!=j 이면 무한대(INF)

2) D[i][j]에 간선정보를 저장

// 경유지 K에 대해서

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

    // 출발 정점 I에서

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

        // 도착 정점 J까지의 최단거리를 아래와같이 갱신

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

            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

        }

    }

}