백준 11404번: 플로이드

문제

문제 바로가기> 백준 11404번: 플로이드

풀이

플로이드-와샬 알고리즘을 이용하여 도시 i에서 j로 가는데 필요한 최소 비용을 구해주었다. 주의 해야할 점은 두 도시를 연결하는 노선은 하나가 아닐 수 있다는 점이다. 따라서 최소가 되는 노선을 선택해주어야 한다.

#include <iostream>
using namespace std;

int cost[101][101]={};
const int INF = 999999999;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n, m; cin >> n >> m;
    int i, j, c;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            if(i==j) cost[i][j]=0;
            else cost[i][j]=INF;
        }
    }
    for(int k=0; k<m; k++){
        cin >> i >> j >> c;
        cost[i][j] = min(cost[i][j], c);
    }
    for(int k=1; k<=n; k++){
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++)
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
        }
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++) {
            if(cost[i][j]==INF) cout << 0 << ' ';
            else cout << cost[i][j] << ' ';
        }
        cout << '\n';
    }
}