백준 11404 플로이드

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

플로이드-워셜 알고리즘을 사용하는 기본문제

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m, a, b, c;
    cin >> n >> m;
    int maxDist = 100000*(n-1)+1;
    vector<vector<int>> dist(n+1, vector<int>(n+1, maxDist));
    for(int i=1; i<=n; i++)
        dist[i][i] = 0;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        if(dist[a][b] > c)
            dist[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(dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];


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

 

초기값에 INT_MAX 사용시 오버플로우 우려가 있어 주어진 조건에서의 최대값을 따로 지정하였다.

 

"시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 라는 설명에 주의하여 입력시 값을 비교한다.