[백준] 11404 : 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

---

• 모든 도시에 대해서 최소 비용을 한번에 구해내는 문제이다.
• 도시의 수가 최대 100개 까지기 때문에, n^3 으로도 충분히 가능할 것으로 보여 플로이드 와샬 알고리즘을 적용시켜주면 간단하게 풀 수 있다.
• 버스 노선은 양방향이 아닌 단방향이므로 한쪽으로만 연결시켜준다.
• 같은 노선이 있을 수 있다고 했으니, 여러 개 나올 경우 그들 중 최소값으로 초기화시키고 돌려준다.

---

#include <iostream>

#define INF 1000000000

using namespace std;

int n, m, a, b, c;
int answer[101][101];

int main(void)
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            answer[i][j] = (i == j ? 0 : INF);      // 행렬 INF 로 초기화
        }
    }

    for(int i = 0 ; i < m ; i++)
    {
        cin >> a >> b >> c;
        if(answer[a][b] > c) answer[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(answer[i][j] > answer[i][k] + answer[k][j])
                {
                    answer[i][j] = answer[i][k] + answer[k][j];
                }
            }
        }
    }

    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            cout << (answer[i][j] == INF ? 0 : answer[i][j]) << " ";    // INF 로 남아있는 값은 연결되지 않는다는 것
        }
        cout << endl;
    }
}