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

 

#include <iostream>
#define INF 987654321
using namespace std;

int n; //도시
int m; //버스
int arr[101][101] = { 0 };
int x, y, z;

int main() {
	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			arr[i][j] = INF;

	for (int i = 1; i <= n; i++)
		arr[i][i] = 0;

	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;

		if (arr[x][y] > z)
			arr[x][y] = z;
	}

	//중간 노드
	for (int k = 1; k <= n; k++) {
		//시작 노드
		for (int i = 1; i <= n; i++) {
			//도착 노드
			for (int j = 1; j <= n; j++) {
				if (arr[i][k] + arr[k][j] < arr[i][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}

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

	return 0;
}

가능성이 여러 가지가 있다면 무한이며

어떤 것이 더 최단거리인지 따져서 값을 채워줘야한다.

일단 모두 무한으로 해두고, 같은 곳에서 같은 곳으로 가는 값은 0으로 채워준다.

무한인 곳에는 입력 받은 비용을 채워주고, 이미 비용이 있다면 더 작은 비용으로 바꾼다.

 

i에서 j로 바로 가는 것이 최단 비용인지, k를 거쳐서 i-k, k-j로 가는 것이 최단 비용인지 계산한다.

그 중 작은 값으로 저장한다.