[백준] 11404 플로이드 C++

플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구하는 알고리즘

풀이 

a->b로 갈때 1~n 사이의 임의의 정수인 k를 들렸다 가는 경우 중에 최솟값으로 비용을 정한다.

주의

길이 없는 경우를 990만 보다 (99X100000) (99개의 노드를 다 들리고 각 간선  간 비용이 최대값일 경우)
작게 잡으면 안된다. (자연수로 설정할 때)

* 그리고 출력할때 한 칸 씩 띄어 출력하라는 말이 없었는데 
붙여서 썼더니 틀렸다

 

1. 길이 없는 경우를 1000000000으로 표현

#include<iostream>
#include<algorithm>

using namespace std;

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

int main()
{
	cin >> n;
	cin >> m;
	//입력   a->b로 가는 버스 중에서 더 짧은것을 입력
	int a, b, cost;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> cost;
		if(!city[a][b] || city[a][b]>cost)//비용은 자연수이므로 0이면 아직 버스가 없다는 뜻
			city[a][b] = cost;
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i != j && city[i][j] == 0)
				city[i][j] = 1000000000;
		}
		
	}
	//모든 경로에 대해  어느 k 지점을 들렸다 가는 비용 계산
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for (int j = 1; j <= n; j++)
			{
				if (i == j || i == k || k == j)
					continue;
				
				city[i][j] = min(city[i][j], city[i][k] + city[k][j]);
			}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (city[i][j] == 1000000000)
				cout << '0';
			else
				cout << city[i][j];
			cout << ' ';
		}
		cout << "\n";
	}

		
}

2. 길이 없는 경우를 -1로 표현

#include<iostream>
#include<algorithm>

using namespace std;

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

int main()
{
	cin >> n;
	cin >> m;
	//입력   a->b로 가는 버스 중에서 더 짧은것을 입력
	int a, b, cost;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> cost;
		if(!city[a][b] || city[a][b]>cost)//비용은 자연수이므로 0이면 아직 버스가 없다는 뜻
			city[a][b] = cost;
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i != j && city[i][j] == 0)
				city[i][j] = -1;
		}
		
	}
	//모든 경로에 대해  어느 k 지점을 들렸다 가는 비용 계산
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for (int j = 1; j <= n; j++)
			{
				if (i == j || i == k || k == j)
					continue;
				if (city[i][k] == -1 || city[k][j] == -1)//길이 없는 경우이므로
					continue;
				if (city[i][j] == -1)//길이 생긴 경우
					city[i][j] = city[i][k] + city[k][j];
				else
					city[i][j] = min(city[i][j], city[i][k] + city[k][j]);
			}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (city[i][j] == -1)
				cout << '0';
			else
				cout << city[i][j];
            cout<<' ';
		}
		cout << "\n";
	}

		
}