🔍 11404 플로이드

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

---

🤔 풀이

• 플로이드 알고리즘을 사용한다.
  - 중간에 거치는 지점을 시작 지점으로 하는 경우는 제외한다.
• 무한대 대신 -1을 넣어 판단한다.
  - 만약 dist[i][j] 값에 무한대를 표시하는 -1이 들어있을 때, 최솟값을 제대로 구하지 못하므로, 무한대(-1)가 들어있는지 확인해야 한다.
• i → m → j 경로에서 i→m 또는 m→j 경로 둘 중 하나라도 무한대의 값을 가지면 해당 경로는 업데이트 될 수 없으므로 넘어간다.

---

📝 코드

#include <iostream>
using namespace std;

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

void floyd(int middle) {
    for (int i = 1; i <= n; i++) {
        if (i != middle) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][middle] == -1 || dist[middle][j] == -1) continue;
                if (dist[i][j] == -1) {
                    dist[i][j] = dist[i][middle] + dist[middle][j];
                }
                else {
                    dist[i][j] =  min(dist[i][j], dist[i][middle] + dist[middle][j]);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    int cost, a, b;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i!=j) dist[i][j] = -1;
        }
    }

    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> cost;
        if (dist[a][b] != -1) dist[a][b] = min(dist[a][b], cost);
        else dist[a][b] = cost;
    }

    for (int i = 1; i <= n; i++) {
        floyd(i);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == -1) cout << 0 << " ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}