[백준] 11404 플로이드

11404번: 플로이드

 

www.acmicpc.net

풀이

'Floyd-Warshall' 알고리즘을 사용하면 쉽게 해결할 수 있는 문제이다.

코드

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int n, m;
int adj[101][101];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) adj[i][j] = INT_MAX;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = min(adj[a][b], c);
    }

    // floyd-warshall 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 출발지와 목적지가 같으면 건너뛴다
                if (i == j) continue;
                // 경유해서 가는 길이 있는 경우
                if (adj[i][k] != INT_MAX && adj[k][j] != INT_MAX)
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << (adj[i][j] == INT_MAX ? 0 : adj[i][j]) << ' ';
        cout << '\n';
    }
}