[백준 / BOJ] C++ 11404 플로이드

11404번: 플로이드

 

문제

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

11404번: 플로이드

 

 

풀이

기본적인 플로이드-워셜 알고리즘을 사용하면 풀 수 있는 문제다. 단, INF인 경우 0을 출력해줘야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, dist[101][101];
  cin >> N >> M;
  // dist 배열 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      dist[i][j] = i == j ? 0 : INF;
      
  // 간선 정보 입력
  for (int i = 1; i <= M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    dist[a][b] = min(dist[a][b], c);
  }
  
  // 플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        
  // 실제 최단 경로
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++)
      cout << (dist[i][j] == INF ? 0 : dist[i][j]) << ' ';
    cout << '\n';
  }
  return 0;
}