백준 / 11404 / 플로이드 / C++

문제 링크 : https://www.acmicpc.net/problem/11404

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    vector<vector<int>> arr(n,vector<int>(n,1000000000));
    int m;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int start,end,val;
        cin >> start >> end >> val;
        if(arr[start - 1][end - 1] > val)
        {
            arr[start - 1][end - 1] = val;
        }
    }
    for(int k = 0; k < n; k++)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j)
                {
                    continue;
                }
                if(arr[i][k] + arr[k][j] < arr[i][j])
                {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(arr[i][j] >= 1000000000)
            {
                cout << 0 << " ";
            }
            else
            {
                cout << arr[i][j] << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

플로이드 - 워셜 알고리즘을 통해 풀었다. 시행착오는 처음 조건에서 갈 수 없는 곳을 0으로 표시한다는 조건을 잊은 것이고, 그 조건을 체크하는 과정에서 INT_MAX를 썼다가 정수 오버플로우를 확인하지 못한 것이다. 적당한 값을 할당해서 해결했다.