[ 백준 11404 ] 플로이드 (c/c++)

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

 

 

[ 문제 요약 ]

버스의 시작 도시, 도착 도시, 비용이 주어질 때, i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용을 출력한다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

 

[ 문제 풀이 ]

1. 우선 모든 도시의 비용을 큰 수로 잡는다.

2. 같은 도시로 가는 경우 비용은 0, 다른 경로의 경우 최초로 주어지는 값으로 초기화한다.

3. 기본값과 한 도시를 경유해서 가는 값 중 저렴한 것으로 저장한다.

4. 모든 도시의 경우를 비교하여 최소값으로 저장한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M, D[111][111];

int main() {
    cin >> N >> M;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) D[i][j] = 1e9;
    for(int i=1; i<=N; i++) D[i][i] = 0;
    for(int i=1; i<=M; i++){
        int s, e, w; cin >> s >> e >> w;
        D[s][e] = min(D[s][e], w);
    }

    for(int k=1; k<=N; k++){
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }

    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            if (D[i][j] == 1e9) cout << "0 ";
            else 
                cout << D[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

 

 

 

[ 주의할 점 ]

기본적인 와셜-플루이드 문제이다. 무한대의 경우가 0으로 출력되어야 함을 조심해야 한다. 100001과 같이 완벽히 크지 않은 수는 계산과정에서 오버될 수 있기 때문에 틀릴 수 있다.