[백준 11404번 / C++ / 플로이드-와샬] 플로이드

이 문제는 플로이드 와샬 알고리즘을 활용해서 풀면 된다. 

플로이드 와샬 알고리즘을 모르는 분은 아래 링크에 들어가서 개념을 보고 오길 권한다. 

24. 플로이드 와샬(Floyd Warshall) 알고리즘

---

#접근방법

 

1. info 이차원 배열에 큰 수로 모두 초기화 한다. 
2. 도시 a에서 a로 가는 정보는 0으로 초기화 한다. 
3. 도시 a에서 도시 b로 가는 비용을 info[a][b]에 담는다. 
4. 도시 a에서 도시 b로 가는 비용과 도시 a에서 도시 k를 거쳤다가 도시 b로 가는 비용을 비교해서 작은값을 info[a][b]에 담는다.
5. 출력

 

 

#include <iostream>
#include <algorithm>
using namespace std; 
int info[101][101];

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

	int n; cin >> n; 
	int m;  cin >> m; 

	fill(info[0], info[101], 987654321); 

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

	for (int i = 0; i < m; i++) {
		int from, to, cost; 
		cin >> from >> to >> cost; 
		info[from][to] =min(info[from][to], cost); 
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				info[i][j] = min(info[i][j], info[i][k] + info[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (info[i][j] == 987654321) cout << "0 "; 
			else cout << info[i][j] << " ";
		}cout << "\n";
	}

	return 0; 
	
}

 

11404번: 플로이드