백준 11780 c++

플로이드 워셜과 재귀함수로 그 경로를 찾는 문제다.
경로 찾는게 너무 어려웠는데 다시 도전하겠다.

#include <iostream>
#include <vector>

#define INF 10000100

using namespace std;

void input_data(vector<vector<int>>& cost)
{
	//cout << "\ninput_data()\n";
	int n, m;
	int i;
	int a, b, c;

	cin >> n;
	cin >> m;
	cost.resize(n + 1, vector<int>(n + 1, INF));//모든 값을 최대 값으로 갱신
	for (i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		if (cost[a][b] > c)//새로운 값이 기존 값보다 작다면
		{
			cost[a][b] = c;//갱신
		}
	}
	for (i = 1; i < cost.size(); i++)
	{
		cost[i][i] = 0;
	}

	return;
}

void floyd_warshall(vector<vector<int>>& cost, vector<vector<int>>& route)
{
	//cout << "\nfloyd_warshall()\n";
	int i, j, k;
	int n = cost.size();
	int temp;

	for (k = 1; k < n; k++)
	{
		for (i = 1; i < n; i++)
		{
			for (j = 1; j < n; j++)
			{
				if (cost[i][k] != INF && cost[k][j] != INF) 
				{
					temp = cost[i][k] + cost[k][j];
					if (temp < cost[i][j]) 
					{
						cost[i][j] = temp;
						route[i][j] = k;
					}
				}
			}
		}
	}

	return;
}

void get_path(int start, int end, vector<vector<int>>& route, vector<int>& path) 
{
	if (route[start][end] == 0)
	{
		return; // 중간에 경유하는 노드가 없으면 종료
	}
	int mid = route[start][end]; // 중간 경유지

	get_path(start, mid, route, path); // 시작점에서 중간점까지의 경로 추가
	path.push_back(mid); // 중간 경유지 추가
	get_path(mid, end, route, path); // 중간점에서 끝점까지의 경로 추가
}

void find_route(vector<vector<int>>& cost, vector<vector<int>>& route)
{
	int n = cost.size();
	int start, end;

	// 모든 i에서 j로 가는 경로를 출력
	for (start = 1; start < n; start++)
	{
		for (end = 1; end < n; end++)
		{
			if (cost[start][end] == INF || start == end)
			{
				cout << "0\n";
				continue; // 경로가 없거나 자기 자신으로 가는 경우는 제외
			}

			vector<int> path;
			path.push_back(start); // 시작점 추가
			get_path(start, end, route, path); // 경로를 추적해서 중간 노드들을 path에 저장
			path.push_back(end); // 끝점 추가

			// 경로 출력
			cout << path.size() << " ";
			for (int node : path) 
			{
				cout << node << " ";
			}
			cout << "\n";
		}
	}

	return;
}

void find_answer(vector<vector<int>>& cost)
{
	//cout << "\nfind_answer()\n";
	int i, j;
	int n = cost.size();
	vector<vector<int>> route(n, vector<int>(n, 0));

	//cout << "플로이드 워셜 수행\n";
	floyd_warshall(cost, route);

	//플로이드 워셜 결과 출력
	for (i = 1; i < n; i++)
	{
		for (j = 1; j < n; j++)
		{
			if (cost[i][j] >= INF)
			{
				cout << "0 ";
			}
			else
			{
				cout << cost[i][j] << " ";
			}
		}
		cout << "\n";
	}

	//플로이드워셜 결과를 통해 얻은 i에서 j로 가는 경로에 포함된 도시의 개수 k와 경로
	//cout << "경로 찾기\n";
	find_route(cost, route);

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<int>> cost;

	input_data(cost);
	find_answer(cost);

	return 0;
}