백준 11404 플로이드 (C++)

11404번: 플로이드

플로이드 워셜 알고리즘 문제이다. 도시 간의 최소 비용을 구하면 되는 문제로 간단하게 풀 수 있다. 주의할 점은 출발 지점과 도착 지점이 같은 버스가 주어질 수도 있는데 이 때는 최소 비용이기에 더 낮은 비용의 값을 저장한다.

#include <iostream>
#include <algorithm>

#define INF 987654321

using namespace std;

int n, m;
int A[100][100];

void solution() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    A[i][j] = 0;
                    continue;
                }
                A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == INF) A[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    cin >> m;

    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            A[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        A[a - 1][b - 1] = min(A[a - 1][b - 1], c);
    }

    solution();

    return 0;
}