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

문제

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

11404번: 플로이드

풀이

플로이드 와샬 알고리즘을 이용해서 푸는 문제이다.

플로이드 와샬은 시작에서 목표로 가는데 이 사이에 어떠한 중간지점을 껴서 가는 게 더 짧다면 이 짧은 거리로 경로를 갱신함으로써 최단 경로를 탐색하는 알고리즘이다.

 

3중 for문을 돌면서 모든 정점을 비교해보면 된다.

입력으로 같은 경로의 다른 비용인 입력이 주어질 수 있으므로,

graph 배열에 저장할 때, 현재 저장되어 있는 값보다 작은지 확인하는 과정이 필요하다.

 

문제를 풀고 제출했는데 계속 97%에서 틀렸습니다가 나와서 질문게시판을 보고 해결했다.

처음에 inf값을 100001으로 줬는데, 이 값은 버스를 한 번 타는데 드는 비용이므로,

여러 번 거친다면 비용이 100001 보다 훨씬 커질 수 있다.

따라서 inf 값을 매우 큰 값으로 줘야 한다.

코드

#include <iostream>

using namespace std;
int graph[101][101];
int inf = 987654321;

int minval(int a, int b) {
    if (a < b) return a;
    else return b;
}

int main() {
    int n, m;
    cin >> n >> m;
    fill_n(&graph[0][0], 101 * 101, inf);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (graph[a][b] > c) graph[a][b] = c;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][k] != inf && graph[k][j] != inf) {
                    graph[i][j] = minval(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] == inf || i == j) cout << "0 ";
            else cout << graph[i][j] << " ";
        }
        cout << '\n';
    }
}