플로이드 2 (feat. 백준, 11780번)

플로이드 2
https://www.acmicpc.net/problem/11780

11780번: 플로이드 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int N, M;
int ans1[101][101];
int ans2[101][101];
deque<int> q;
void solve(register int f, register int t) {
	if (ans2[f][t] == 0)
		q.push_back(f), q.push_back(t);
	else {
		solve(f, ans2[f][t]);
		q.pop_back();
		solve(ans2[f][t], t);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			ans1[i][j] = static_cast<int>(1e9);
	for (register int m = 0, x, y, c; m < M; ++m)
		cin >> x >> y >> c, ans1[x][y] = min(ans1[x][y], c);
	for (register int m = 1, f, t; m <= N; ++m)		// mid
		for (f = 1; f <= N; ++f)						// from
			for (t = 1; t <= N; ++t)					// to
				if (f != t && ans1[f][t] > ans1[f][m] + ans1[m][t])
					ans1[f][t] = ans1[f][m] + ans1[m][t], ans2[f][t] = m;
	for (register int i = 1, j; i <= N; ++i) {
		for (j = 1; j <= N; ++j)
			if (ans1[i][j] == static_cast<int>(1e9))
				cout << "0 ";
			else
				cout << ans1[i][j] << " ";
		cout << "\n";
	}
	for (register int i = 1, j; i <= N; ++i) {
		for (j = 1; j <= N; ++j) {
			if (ans1[i][j] == static_cast<int>(1e9))
				cout << "0 ";
			else {
				solve(i, j);
				cout << q.size() << " ";
				for (auto& v : q)
					cout << v << " ";
				q.clear();
			}
			cout << "\n";
		}
	}
	return 0;
}
// *&)*@*

이전 '플로이드' 문제에서 이동 경로에 대한 모든 과정도 출력하는 문제입니다.

'플로이드' 를 풀지 못하셨다면 먼저 풀어보시길 권장합니다.

이동 경로는 검색하여 찾아본터라 설명은 생략하겠습니다.

플로이드 (feat. 백준, 11404번)