[백준] 11404 플로이드 - 플로이드

[ 문제링크 ]

https://www.acmicpc.net/problem/11404

 

🚩 조건

1. 모든 도시의 쌍에 대해 필요한 비용의 최솟값을 구해라

 

 

🚩 접근

1 -> 플로이드 알고리즘 이용하자! (삼중for문 쓰면 됨)

 

 

🚩 시행착오

1. 처음에 전역변수로 배열을 선언하고 아래와 같이 초기화했는데, 이러면 첫번째 원소만 해당 값으로 지정된다고 한다.
   => 특정값으로 초기화하려면 for문 등의 방식을 사용해야 한다.

   int table[101][101] = { 100001 };	// 잘못된 초기화 방식

2. 계속 98%정도에서 "틀렸습니다"가 나왔다.. 그 이유는 "비용은 100,000보다 작거나 같은 자연수이다."라는 조건 때문에 위처럼 배열의 초기값을 100,001로 설정했기 때문이었다.
   => 도시의 최대값이 100, 비용의 최대값이 100,000이므로 어떤 도시로 이동하는데 필요한 최대 비용은 100,000 * 99이다. 따라서 초기 INF의 값은 그 이상으로 잡아야 한다.

 

💻 코드 (C++)

#include <iostream>
using namespace std;

int table[101][101];
int main() {
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			if (i == j) table[i][j] = 0;
			else table[i][j] = 100000 * 100;
		}
	}

	int n, m;
	cin >> n >> m;
	
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (table[a][b] < c) continue;
		table[a][b] = c;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (j == i || k == i || j == k) continue;
				if (table[j][k] > table[j][i] + table[i][k]) {
					table[j][k] = table[j][i] + table[i][k];
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (table[i][j] == 100000*100) {
				cout << 0 << " ";
				continue;
			}
			cout << table[i][j] << " ";
		}
		cout << "\n";
	}
}