[백준 11780] 플로이드 2 (C++)

이 문제는 플로이드 워셜 알고리즘으로 한 정점에서 다른 정점으로의 최소 비용을 구하고 경로 복원을 해야하는 문제이다.

먼저, w[s][t]는 s에서 t로의 최소 비용을 저장하고, nxt[s][t]는 s에서 t로의 최소 비용이 되도록 하기 위해서 방문해야하는 다음 노드를 저장한다고 하자.

그렇다면, w[s][t]보다 w[s][k] + w[k][t]가 작다면, 정점 k를 경유하는 것이 빠르므로 w[s][t를 w[s][k] + w[k][t]로 변경하고, 정점 k를 경유하도록 하기 위해, nxt[s][t]를 k로 변경해야한다.

이후, 정점 s에서 정점 t로의 경로 복원 시에는 s와 t가 같아질 때까지, s를 출력하고 s를 nxt[s][t]로 변경해나가면 된다.

경로를 구성하는 정점 갯수를 출력하고 경로를 출력해야하므로, 벡터에 경로를 저장해 두는 것이 유리할 것이다.

플로이드 워셜의 시간 복잡도는 $O(V^3)$이고, 경로 복원의 시간 복잡도는 $O(V^2K)$이므로 전체 시간 복잡도는 $O(V^3)$이 되며 시간 내에 답을 구할 수 있다.

이를 바탕으로 코드를 작성해보자.

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

const int INF = 1e9;
int n, m;
int w[101][101], nxt[101][101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i <= 100; i++) {
		fill(w[i], w[i] + 101, INF);
		w[i][i] = 0;
	}

	cin >> n >> m;
	for (int i = 0, a, b, c; i < m; i++) {
		cin >> a >> b >> c;
		if (w[a][b] > c) {
			w[a][b] = c;
			nxt[a][b] = b;
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (w[i][j] > w[i][k] + w[k][j]) {
					w[i][j] = w[i][k] + w[k][j];
					nxt[i][j] = nxt[i][k];
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (w[i][j] == INF) cout << 0 << " ";
			else cout << w[i][j] << " ";
		}
		cout << "\n";
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (w[i][j] == 0 || w[i][j] == INF) {
				cout << 0 << "\n";
				continue;
			}
			vector<int> v;
			int s = i;
			while (s != j) {
				v.push_back(s);
				s = nxt[s][j];
			}
			if (!v.empty()) v.push_back(s);
			cout << v.size() << " ";
			for (int x : v) cout << x << " ";
			cout << "\n";
		}
	}
}