[c++/백준] 11404번: 플로이드

문제 링크

11404번: 플로이드

풀이

플로이드를 이용하는 문제
플로이드의 핵심은 경유와 모든 노드에서의 최소 비용(거리)

1. 시작 도시와 출발 도시, 비용을 입력 받는데, 노선이 하나가 아닐 수 있으므로 작은 값으로 받는다.
2. 플로이드의 점화식은 arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j])
i는 출발 도시, j는 도착 도시, k는 경유 도시인데, 출발에서 도착까지의 거리와 경유하는 경우를 비교해서 갱신한다.
3. arr[i][j]가 INF보다 크거나 같다면 0을 넣고 출력한다.

⚠ 주의사항

• INF는 100000*100 이상이어야 함
• 시작 도시와 도착 도시를 잇는 버스의 노선이 하나가 아니라는 것
• 갈 수 없는 경우는 0을 출력

코드

#include <iostream>
#include <vector>
#define INF 100000000

using namespace std;

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

	vector<vector<int>> arr(n+1,vector<int>(n+1,INF));
	for (int i = 0;i < m;i++) {
		int st, ar, co;
		cin >> st >> ar >> co;
		arr[st][ar] = min(arr[st][ar], co);
	}
	for (int i = 1;i <= n;i++) { 
		arr[i][i] = 0;
	}

	for (int k = 1;k <= n;k++) { //경유
		for (int i = 1;i <= n;i++) { //출발
			for (int j = 1;j <= n;j++) { //도착
				arr[i][j] = min(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) arr[i][j] = 0;
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}