백준 1507 c++

플로이드 워셜 결과를 바탕으로 원래 배열을 찾아내는 문제이다.
이걸 몰라서 이미 플로이드 워셜 결과를 또 반복했다.
각 알고리즘의 역에 대해서도 연습할 필요가 있을거 같다.

#include <iostream>
#include <vector>

using namespace std;

void input_data(vector<vector<int>>& city, vector<vector<int>>& origin_city)
{
	cout << "\ninput_data()\n";
	int N, i, j, temp;

	cin >> N;
	city.resize(N + 1, vector<int>(N + 1, 0));
	origin_city.resize(N + 1, vector<int>(N + 1, 0));
	for (i = 1; i < city.size(); i++)
	{
		for (j = 1; j < city.size(); j++)
		{
			cin >> temp;
			city[i][j] = temp;
			origin_city[i][j] = temp;
		}
	}

	cout << "입력결과\n";
	for (i = 1; i < city.size(); i++)
	{
		for (j = 1; j < city.size(); j++)
		{
			cout << city[i][j] << " ";
		}
		cout << "\n";
	}

	return;
}

//입력 결과가 이미 플로이드 와샬이 적용된 결과이다. 
//구해야 하는 값은 플로이드 와샬 결과값을 기반으로 원래 도로가 몇개인지 찾는거임
//그럼 역 알고리즘인가?
bool reverse_floyd_warshall(vector<vector<int>>& city, vector<vector<int>>& origin_city)
{
	cout << "\nreverse_floyd_warshall()\n";
	int i, j, k, N = city.size();

	for (k = 1; k < N; k++)
	{
		for (i = 1; i < N; i++)
		{
			for (j = 1; j < N; j++)
			{   
				if (k == i || k == j)
				{
					continue;
				}
				if (city[i][j] > city[i][k] + city[k][j])//플로이드 워셜 결과에서 경유하는 경로가 더 클 수 없다.
				{
					return false;
				}
				if (city[i][j] == city[i][k] + city[k][j])
				{
					origin_city[i][j] = 0;
				}
			}
		}
	}

	cout << "역 플로이드 워셜 결과\n";
	for (i = 1; i < N; i++)
	{
		for (j = 1; j < N; j++)
		{
			cout << origin_city[i][j] << " ";
		}
		cout << "\n";
	}

	return true;
}

int find_answer(vector<vector<int>>& city, vector<vector<int>>& origin_city)
{
	cout << "\nfind_anwer()\n";
	bool able;
	int answer = 0, N = city.size(), i, j;

	able = reverse_floyd_warshall(city, origin_city);
	if (!able)
	{
		answer = -1;
	}
	else
	{
		for (i = 1; i < N; i++)
		{
			for (j = 1; j < N; j++)
			{
				answer += origin_city[i][j];
			}
		}
		answer /= 2;
	}
	
	return answer;
}


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

	vector<vector<int>> city;
	vector<vector<int>> origin_city;

	input_data(city, origin_city);
	cout << find_answer(city, origin_city) << "\n";

	return 0;
}