백준 11404 플로이드 C++

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

상관없는지 모르겠으나 원래는 kij순으로 루프 돌아야한다

문제 이름에서부터 플로이드 와샬 알고리즘을 사용해야 한다는 것을 암시하고 있는 문제이다.

주의할 것은, 이전까지 INF 값으로 limits.h 헤더에 있는 INT_MAX를 사용했는데, 이 값에 어떤 값이 더해지는 연산을 하게되면 오버플로우가 발생한다.

다익스트라, 벨만포드에서는 괜찮았지만 플로이드에서 이런 일이 생기니, 그냥 속편하게 내가 INF를 지정해서 써야겠다.

INF는 항상 (간선 가중치의 최댓값 ) * (정점 개수 - 1 ) 보다 크게 잡아줘야 한다.

#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
int n, m;
int dis[101][101];
const int MAX = 1000000000; //INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값
void FW() {
    for (int k = 1; k <= n; k++) 
        for (int j = 1; j <= n; j++) 
            for(int i = 1; i <= n; i++) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
 
int main(void) {
    //ios::sync_with_stdio(false);
    cin.tie(0);
        
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            dis[i][j] = i == j ? 0 : MAX;
        
    for (int i = 0; i < m; i++) {
        int src, dst, cost;
        cin >> src >> dst >> cost;
        dis[src][dst] = min(dis[src][dst], cost);
    }
 
    FW();
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] == MAX) dis[i][j] = 0;
             cout << dis[i][j] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}