백준 11404번 : 플로이드

문제 링크 : www.acmicpc.net/problem/11404

풀이에 참고한 링크 : www.acmicpc.net/board/view/32191

내 풀이(2021.1.26.) :

#include <iostream>
#include <limits.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V 100 // 노드 개수의 최대값

int V, E; // V : 노드의 개수, E : 간선의 개수
vector<vector<int>> VV_info(MAX_V + 1, vector<int>(MAX_V + 1, INT_MAX)); // 모든 노드에서 모든 노드까지의 최단 거리

void floyd_warshall() { // 플로이드 워셜
	// 자기 자신에게 가는 간선값은 0
	for (int i = 1; i <= V; i++) {
		VV_info[i][i] = 0;
	}
	
	// 점화식 수행
	for (int k = 1; k <= V; k++) {
		for (int a = 1; a <= V; a++) {
			for (int b = 1; b <= V; b++) {
				if (VV_info[a][k] != INT_MAX && VV_info[k][b] != INT_MAX) {
					VV_info[a][b] = min(VV_info[a][b], VV_info[a][k] + VV_info[k][b]);
				}
			}
		}
	}
}

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

	cin >> V >> E;
	// 노드/간선 정보 초기화
	for (int i = 0; i < E; i++) {
		int a, b, c; cin >> a >> b >> c;
		VV_info[a][b] = min(VV_info[a][b], c);
	}

	floyd_warshall();

	for (int a = 1; a <= V; a++) {
		for (int b = 1; b <= V; b++) {
			int dist = VV_info[a][b];
			if (dist == INT_MAX) cout << "0 ";
			else cout << dist << " ";
		}
		cout << "\n";
	}

	return 0;
}

"시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 라는 조건에 유의한다.

즉, 간선값을 초기화할 때 min값인지 아닌지 확인 후 저장해야 한다.