백준] 11404 - 플로이드

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

출력

N개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

소스코드

#include <iostream>
#define INF 1000000000
using namespace std;
int graph[100][100], n;
void Floyd()
{
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (graph[i][k] + graph[k][j] < graph[i][j])
					graph[i][j] = graph[i][k] + graph[k][j];
}
int main(void)
{
	int b, v1, v2, w;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			graph[i][j] = INF;
	for (int i = 0; i < n; i++)
		graph[i][i] = 0;
	cin >> b;
	for (int i = 0; i < b; i++)
	{
		cin >> v1 >> v2 >> w;
		if (graph[v1 - 1][v2 - 1] > w)
			graph[v1 - 1][v2 - 1] = w;
	}
	
	Floyd();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (graph[i][j] == INF)
				cout << '0 ';
			else
				cout << graph[i][j] << ' ';
		}
		cout << '\n';
	}
}

Tip

플로이드-워셜(Floyd-Warshall) 알고리즘을 구현하는 문제로, 동적계획법 중 하나다. 방법만 알면 어려운 부분은 없지만 경로가 없을 때의 초기값을 적절히 설정해 오버플로우가 발생해서 문제를 일으키지 않도록 해야 한다.