백준 No.11404 [플로이드]

BOJ No.11404 [플로이드]

Floyd-Warshall Algorithm

---

 Problem 

11404번: 플로이드

---

 Code 

#include <iostream>
#include <vector>
 
using namespace std;
typedef unsigned long long ull;
 
int V, E;
const ull INF = ull(1e15);
vector<vector<ull>> floyd;
 
int main() {
    cin >> V >> E;
    floyd.assign(V + 1, vector<ull>(V + 1, INF));
 
    for (int i = 1; i <= V; i++) floyd[i][i] = 0;
 
    for (int i = 0; i < E; i++) {
        ull s, e, cst;
        cin >> s >> e >> cst;
 
        floyd[s][e] = min(floyd[s][e], cst);
    }
 
    for (int visit = 1; visit <= V; visit++) {
 
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i != visit && j != visit) {
                    floyd[i][j] = min(floyd[i][j], floyd[i][visit] + floyd[visit][j]);
                }
            }
        }
 
    }
 
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++)
            cout << (floyd[i][j] != INF ? floyd[i][j] : 0) << ' ';
        cout << '\n';
    }
}

---

 How to solve 

  Floyd-Warshall Algorithm에 대해서 가장 기본적인 문제이다. 문제의 조건에서, 두 vertex 사이 edge가 여러개 있을 수 있다고 했으므로 #21 line 에선 floyd[ s ][ e ] 에 현재 floyd[ s ][ e ]의 값과 현재 입력된 값인 cst중 더 작은 값으로 floyd[ s ][ e ]를 갱신해 주었다.

 

  Floyd-Warshall Algorithm를 참고하면 된다.