C++ / 백준 / 11404 / 플로이드

문제

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

문제풀이

 

제목 그대로 플로이드 와샬 문제이다.

도시는 n개가 주어지고 버스는 m개가 주어진다.

 

주의해야 할 점은 예제를 보면 같은 시작 도시, 같은 도착 도시가 나올 수 있다. (1, 4, 1), (1, 4 ,2)

그래서 값을 입력받을 때마다 최솟값을 벡터에 저장해줘야 한다.

그리고 i에서 i를 포함하여 i에서 j를 갈 수 없는 경우는 그 자리에 0을 출력해줘야 한다.

 

비용은 100,000 이하이고 도시의 최대 개수는 100개 이므로 100,000 * 100 +1을 MAX로 잡았다.

값을 입력받고 i에서 i로 가는 모든 버스를 0으로 초기화한다.

 

삼중 반복문을 통해 플로이드 와샬 알고리즘을 사용한다.

반복문이 끝났으면 출력할 차례이다.

i에서 i로 가는 부분은 이미 0으로 초기화했으므로,

i에서 i로 가는 경우를 제외하고 남은 i에서 j로 갈 수 없는 부분은 처음에 초기화한 MAX로 되어있을 것이다.

따라서 조건문을 이용해 값이 MAX인 경우 0으로 바꿔준다.

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10000001
using namespace std;

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

	int n(0), m(0), idx(0), city1(0), city2(0), mid(0), cost(0);
	cin >> n >> m;
	vector<vector<int>>bus(n + 1, vector<int>(n + 1, MAX));
	for (idx = 0; idx < m; ++idx) {
		cin >> city1 >> city2 >> cost;
		bus[city1][city2] = min(bus[city1][city2], cost);
	}



	for (city1 = 1; city1 <= n; ++city1) {
		bus[city1][city1] = 0;
	}

	for (mid = 1; mid <= n; ++mid) {
		for (city1 = 1; city1 <= n; ++city1) {
			for (city2 = 1; city2 <= n; ++city2) {
				bus[city1][city2] = min(bus[city1][city2], bus[city1][mid] + bus[mid][city2]);
			}
		}
	}

	for (city1 = 1; city1 <= n; ++city1) {
		for (city2 = 1; city2 <= n; ++city2) {
			if (bus[city1][city2] == MAX) {
				bus[city1][city2] = 0;
			}
			cout << bus[city1][city2] << ' ';
		}
		cout << '\n';
	}
}