백준 11404번: 플로이드 (C++)

문제링크

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

풀이방법

해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하는 문제이다. 해당 문제에 대한 상세 풀이나 플로이드 알고리즘에 대한 이해가 필요하면 아래 영상을 참고하자.

https://www.youtube.com/watch?v=dDDy2bEZRA8

코드

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

const int INF = 0x3f3f3f3f;
int d[105][105];
int n, m;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
    fill(d[i], d[i]+1+n, INF);
  while(m--){
    int a,b,c;
    cin >> a >> b >> c;
    d[a][b] = min(d[a][b], c);
  }
  for(int i = 1; i <= n; i++) d[i][i] = 0;

  for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++)
        d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
  
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      if(d[i][j] == INF) cout << "0 ";
      else cout << d[i][j] << ' ';
    }
    cout << '\n';
  }
}