BOJ 11404 플로이드

1 개요

BOJ 11404 플로이드

• 백준 온라인 저지 11404번 문제
• BOJ 32단계

2 같이 보기

• BOJ 11780 플로이드 2

3 C++

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;

int n, m;
int A[101][101];
int INF = INT_MAX;

void solve() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i != j && A[i][j] == 0) A[i][j] = INF;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = 1; k <= n; k++) {
        if (A[j][i] != INF && A[i][k] != INF) {
          A[j][k] = min(A[j][i] + A[i][k], A[j][k]);
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (A[i][j] == INF) A[i][j] = 0;
      cout << A[i][j] << ' ';
    }
    cout << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  int a, b, c;
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    if (A[a][b] != 0) {
      A[a][b] = min(A[a][b], c);
    } else {
      A[a][b] = c;
    }
  }
  solve();
}