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

문제링크

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

풀이방법

해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하고 단순히 최단 거리 뿐만 아니라 특정 노드에서 노드로 이동하는 최단 경로가 어떻게 진행되는지도 출력해야 하는 문제다. 따라서 경로 복원에 필요한 nxt배열을 추가로 삽입하여 문제를 해결할 수 있다.
해당 문제에 대한 상세 풀이는 아래 바킹독님 영상을 참고하자. 또한 플로이드 알고리즘이나 경로 복원에 대한 개념이 부족하면 아래 영상을 통해 알고리즘에 대한 개념을 익히자.

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

코드

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

const int INF = 0x3f3f3f3f;
int d[105][105];
int nxt[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);
    nxt[a][b] = b;
  }
  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++)
        if(d[i][k] + d[k][j] < d[i][j]){
          d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
          nxt[i][j] = nxt[i][k];
        }
  
  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';
  }

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      if(d[i][j] == 0 || d[i][j] == INF){
        cout << "0\n";
        continue;
      }
      vector<int> path;
      int st = i;
      while(st != j){
        path.push_back(st);
        st = nxt[st][j];
      }
      path.push_back(j);
      cout << path.size() << ' ';
      for(auto x : path) cout << x << ' ';
      cout << '\n';
    }
  }
}