[백준/BOJ] 백준 11404번 : 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

입력받을 때 a도시에서 b도시로 가는 노선이 하나가 아닐 경우, 비용이 더 작은 것을 저장한다. 플로이드 알고리즘을 사용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int adj[101][101];

void Solve()
{
	//플로이드 알고리즘을 이용하여 각 도시까지 이동하는데 최소 비용을 구한다
	for (int i = 1; i <= n; i++)
		adj[i][i] = 0;
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

	//출력
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			//i에서 j에서 갈 수 없을때는 0을 출력
			if (adj[i][j] == 987654321)
				cout << 0 << " ";

			else
				cout << adj[i][j] << " ";
		}
		cout << "\n";
	}
}

void Pre()
{
	//초기화로 모든 도시로 이동하는 비용을 매우 큰 수로 저장해 놓는다
	// 매우 큰 수일때는 갈 수 없다고 한다
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++)
			adj[i][j] = 987654321;
}

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

	Pre();

	int a, b, c;

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;

		//시작도시와 도착도시를 연결하는 노선이 하나가 아닐 수 있으므로
		//더 작은값을 저장한다
		if (adj[a][b] > c)
			adj[a][b] = c;
	}

	Solve();

	return 0;
}