이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 26 번째 글 입니다.
목차
실버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;
}