[백준 11404 | C++] 플로이드 :: 플로이드-워셜

• 문제 링크 : 11404번: 플로이드
• 문제 태그 : 그래프 이론, 최단 경로, 플로이드-워셜

 

플로이드-워셜 개념 문제였습니다. 이 과정에서 특이한 점을 발견해서 두 번 제출했습니다.

 

풀이1

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int INF = 1 << 30;

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

	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> g(n + 1);
	vector<vector<int>> ans(n + 1, vector<int>(n + 1, INF));
	for (int i = 0;i < m;i++) {
		int a, b, c;
		cin >> a >> b >> c;

		g[a].push_back({ b, c });
		if (ans[a][b] > c) {
			ans[a][b] = c;
		}
	}

	for (int i = 1;i <= n;i++) {
		ans[i][i] = 0;
	}

	for (int k = 1;k <= n;k++) {	
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				if (ans[i][k] != INF && ans[k][j] != INF && 
					ans[i][k] + ans[k][j] < ans[i][j]) {
					ans[i][j] = ans[i][k] + ans[k][j];
				}
			}
		}
	}

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

 

 

풀이2

그래프 문제라서 당연히 인접리스트를 구성했는데, 사실은 필요하지 않은 내용이었습니다. 

대신 인접 행렬을 통해 구성하였습니다.

• 참고 글 : 플로이드-워셜 알고리즘 (Floyd-Warshall)

플로이드-워셜 알고리즘 (Floyd-Warshall)

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int INF = 1 << 30;

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

	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> g(n + 1);
	vector<vector<int>> ans(n + 1, vector<int>(n + 1, INF));
	for (int i = 0;i < m;i++) {
		int a, b, c;
		cin >> a >> b >> c;

		g[a].push_back({ b, c });
		if (ans[a][b] > c) {
			ans[a][b] = c;
		}
	}

	for (int i = 1;i <= n;i++) {
		ans[i][i] = 0;
	}

	for (int k = 1;k <= n;k++) {	
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				if (ans[i][k] != INF && ans[k][j] != INF && 
					ans[i][k] + ans[k][j] < ans[i][j]) {
					ans[i][j] = ans[i][k] + ans[k][j];
				}
			}
		}
	}

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