BOJ 9694 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

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

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

간단한 최단경로 + 역추적 문제입니다. 제한이 작아서 매 테스트케이스마다 플로이드-워셜을 이용해 최단거리를 해주고 역추적으로 경로를 구하면 됩니다. 역추적은 정점 $i$에서 정점 $j$로 최단거리로 가는 길에 거쳐야 하는 정점을 기록해주고, 이를 기준으로 분할정복해서 구하면 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, m, graph[22][22], memo[22][22];
vector<int> ans;

void trace(int s, int e) {
  if (memo[s][e] == -1) return;
  trace(s, memo[s][e]);
  ans.push_back(memo[s][e]);
  trace(memo[s][e], e);
}

int32_t main(void) {
  FastIO;
  T = 1;
  cin >> T;

  for (int _ = 1; _ <= T; _++) {
    cout << "Case #" << _ << ": ";

    cin >> n >> m;

    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) graph[i][j] = 987654321;
    memset(memo, -1, sizeof(memo));

    for (int i = 0; i < n; i++) {
      int a, b, x;
      cin >> a >> b >> x;
      graph[a][b] = x;
      graph[b][a] = x;
    }

    for (int k = 0; k < m; k++) {
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
          if (graph[i][k] + graph[k][j] < graph[i][j]) {
            graph[i][j] = graph[i][k] + graph[k][j];
            memo[i][j] = k;
          }
        }
      }
    }

    if (graph[0][m - 1] >= 987654321) {
      cout << -1 << endl;
      continue;
    }

    ans.clear();
    ans.push_back(0);
    trace(0, m - 1);
    ans.push_back(m - 1);

    for (auto x : ans) cout << x << ends;
    cout << endl;
  }

  return 0;
}