백준 11404 - 플로이드 [C++]

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

11404번: 플로이드

---

풀이 과정

도시와 도시 사이를 오가는 버스의 비용이 주어질 때, 모든 도시의 쌍 (A, B)에 대해 A에서 B로 가는 최소 비용을 구하는 문제이다.

 

도시는 정점, 버스의 비용은 가중치를 갖는 간선으로 생각하면 하나의 그래프로 모델링할 수 있고, 그래프의 모든 정점의 쌍에 대한 최소 비용을 구하는 문제로 생각할 수 있다.

 

그래프의 최소 비용 문제에서는 BFS, 다익스트라, 벨만-포드, 플로이드-와샬 알고리즘을 생각해 볼 수 있으며 그중에서 모든 정점의 쌍에 대한 최소 비용은 플로이드-와샬 알고리즘을 사용해서 구할 수 있음이 알려져 있다.

 

플로이드-와샬 알고리즘을 사용하여 문제를 해결하였다.

---

소스 코드

#include <iostream>
#include <vector>
using namespace std;

const int INF = 987654321;
int d[105][105];

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

    int n, m;
    cin >> n >> m;

    for (int i = 1 ; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    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] == INF) cout << "0 ";
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}