(11404) 플로이드

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

단계별로 풀어보기

29단계(최단 경로) 6번째

 

 

 

시작 정점이 정해진 다익스트라, 벨먼-포드와 달리 모든 정점 쌍에 대해 최단거리를 구하는 플로이드-워셜 알고리즘이다.

개인적으로 여러 그래프 순회 알고리즘 중에서도 가장 보기 힘든 것 같다.

시간복잡도도 O(N^3)으로 크고(단순히 큰 게 문제가 아니라, 그래프 문제이면서 N의 범위가 작으면 플로이드를 써야 한다는 것을 들키기 쉽다.) 구현 방식도 단순히 for문을 3번 중첩한 것 뿐이기 때문이다.

플로이드에서 자기 자신인 dist[a][a]는 0으로 초기화해야 하지만, 여기서는 불가능한 경우에도 0을 출력하도록 했기 때문에 안 해도 괜찮았다. 보통은 이렇지 않은 경우가 더 많으니 초기화해주는 것이 좋다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 10000001

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector dist(n+1, vector<int> (n+1, INF));
  
  while(k--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    dist[a][b]= min(dist[a][b], c);
  }
  
  for(int m=1;m<=n;m++){
    for(int s=1;s<=n;s++){
      for(int e=1;e<=n;e++){
        dist[s][e]= min(dist[s][e], dist[s][m]+dist[m][e]);
      }
    }
  }
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cout << (i==j||dist[i][j]==INF ? 0 : dist[i][j]) << " ";
    }
    cout << "\n";
  }
  
  return 0;
}