백준 11780번 - C++

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

const int INF = 0x3f3f3f3f;
int v[105][105];
int nxt[105][105];

int n, e;
int a, b, c;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> e;
	for (int i = 1; i <= n; i++)
		fill(v[i], v[i] + 1 + n, INF);
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		v[a][b] = min(v[a][b], c);
		nxt[a][b] = b;
	}
	for (int i = 1; i <= n; i++) v[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 (v[i][j] > v[i][k] + v[k][j]) {
					v[i][j] = v[i][k] + v[k][j];
					nxt[i][j] = nxt[i][k];
				} 
			}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j] == INF) cout << "0 ";
			else cout << v[i][j] << ' ';
		}
		cout << '\n';;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j] == 0 || v[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';
		}
	}
}