백준, BOJ, 11403번, 플로이드 : C++ [CPP] ★★★★

플로이드 문제를 하나 더 살펴봤다

이것이 더욱 플로이드 알고리즘의 핵심인 최단거리에 가까울 것이다.

 

역시 노드는 100개정도로 별로 없다.

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>

#define MAX 105
#define INF 123456789

using namespace std;

int n, m;

int path[MAX][MAX];

int main() {
    cin >> n >> m;
    //테이블 초기화(처음엔 모두 INF) (1부터 n까지)
    for (int i = 1; i <= n; i++) {
        fill(path[i], path[i]+n+1, INF);
    }

    for (int i = 0; i < m; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        path[from][to] = min(cost, path[from][to]); //방향 그래프
    }

    //자기 자신으로 돌아오는 경로도 있어서 초기화 시켜줘야함 최단 경로 0으로
    for (int i = 1; i <= n; i++) path[i][i] = 0;
    


    //플로이드 알고리즘 
    //i -> k -> j
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                path[i][j] = min(path[i][k]+path[k][j], path[i][j]);
            }
        }
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (path[i][j] == INF) cout << 0 << ' ';
            else cout << path[i][j] << ' ';
        }
        cout << '\n';
    }


}