🥚

Recent Notes

See 20 more →

BOJ - 플루이드(11404)

2 min read

실버1 : 최단경로 문제이다.

생각

dp[i][j] = i에서 j까지 가는데 필요한 최소 비용

dp[i][j] = dp[i][k] + dp[k][j]

Code

//
//  main.cpp
//  algorithm_prac
//
//  Created by 최완식 on 2021/04/05.
//
 
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 100000000;
int N = 0, M = 0;
int cost[101][101];
// dp[k][i][j] = i에서 j로 이동하는 최단 경로, 단 k까지의 노드만을 사용해서
// dp[0][i][j]
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                cost[i][j] = 0;
            } else {
                cost[i][j] = inf;
            }
        }
    }
    
    for (int m = 0; m < M; m++) {
        int a, b, c;
        cin >> a >> b >> c;
        cost[a][b] = min(cost[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 (cost[i][j] > cost[i][k] + cost[k][j]) {
                    cost[i][j] = cost[i][k] + cost[k][j];
                }
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (cost[i][j] == inf) cost[i][j] = 0;
            cout << cost[i][j] << " ";
        }
        cout << '\n';
    }
    
    return 0;
}

Reference

Graph