백준 11404 c++

플로이드 와셜 알고리즘을 사용한 문제풀이다.
처음에는 다익스트라 알고리즘을 사용해 보려 했지만, 다익스트라 알고리즘은 "한" 노드에 대해서 다른 노드까지의 최단경로를 출력하는 알고리즘이라 모든 점에 대해서 확인하려면 오랜 시간이 걸린다.
플로이드 와셜은 "모든" 노드에서 다른 모든 노드까지의 최단경로를 모두 출력하는 알고리즘이다.
DP문제에 더 가깝다고 생각한다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 10000000

using namespace std;

void input_graph(vector <vector<int>> &graph)
{
	int i;
	int n, m;
	int a, b, c;
	//플로이드 와샬 알고리즘을 사용할 것이다.

	cin >> n >> m;
	graph.resize(n, vector<int>(n, INF + 1));
	for (i = 0; i < n; i++)
	{
		graph[i][i] = 0;
	}
	for (i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		graph[a - 1][b - 1] = min(c, graph[a - 1][b - 1]);//이미 저장된 값이 새로 입력된 값보다 크다면 //새로 입력된 값으로 초기화
	}
	/*for (int i = 0; i < graph.size(); i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}*/

	return;
}

void find_answer(vector <vector<int>>& graph)//aka floydwarshall
{
	//쿠르스칼은 전체를 한 트리로 만드는데 필요한 최소비용
	//다익스트라 : 가중치를 포함한 그래프의 '한' 정점에서 다른 모든 정점으로 가는 최단경로
	//플로이드 와샬 알고리즘 : 가중치를 포함한 그래프의 '모든' 정점에서 다른 모든 정점까지의 최단거리...
	int i, j, k;
	vector <vector<int>> answer = graph; //깊은복사
	int num = graph.size();
	int temp;

	//k = 거쳐가는 노드
	for (k = 0; k < num; k++)
	{
		for (i = 0; i < num; i++)
		{
			for (j = 0; j < num; j++)
			{
				temp = answer[i][k] + answer[k][j];
				if (temp < answer[i][j])
				{
					answer[i][j] = temp;
				}
			}
		}
	}

	for (i = 0; i < num; i++)
	{
		for (j = 0; j < num; j++)
		{
			//오류가 발생하는 원인??? 
			//-> 최단거리 입력값 제한이 100000 이하일 뿐, 최단거리 비용은 100000을 넘길 수 있다?
			//연결되지 않은 경우를 어떻게 구분할까
			//총 비용은 100000을 넘겨도 된다...
			//단 100000 * 100 == 10000000은 넘기면 안된다.
			if (answer[i][j] > INF)
			{
				cout << "0 ";
				continue;
			}
			cout << answer[i][j] << " ";
		}
		cout << "\n";
	}

	return;
}

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

	vector <vector<int>> graph;

	input_graph(graph);
	find_answer(graph);

	return 0;
}