BOJ 11404 - 플로이드

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

 

접근

모든 도시끼리 이동하는 비용 최솟값을 구하는 문제이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

따라서, 모든 노드를 거쳐 시작 도시와 도착 도시를 이동하는 모든 노선을 확인해야 한다.

이를 구현하기 적합한 알고리즘은 플로이드 와샬이다.

 

플로이드 와샬을 통해 중간 노드를 거쳐가는 모든 노선을 확인해보도록 하자.

알고리즘은 매우 간단하다.

 

당연하지만, 시작 노드와 도착 노선 그리고 중간 노드를 모두 확인하기에 O(N^3)이 걸린다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX 9999999

int n, m;
int res[101][101];

void init() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			res[i][j] = MAX;
		}
	}
}

void input() {
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		res[a][b] = min(res[a][b], c);
	}
}

void output() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (res[i][j] == MAX) {
				cout << "0 ";
			}
			else {
				cout << res[i][j] << " ";
			}
		}
		cout << "\n";
	}
}

void floydWarshall() {
	init();
	input();
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					continue;
				}

				if (res[i][k] + res[k][j] < res[i][j]) {
					res[i][j] = res[i][k] + res[k][j];
				}
			}
		}
	}
	output();
}

int main() {
	cin >> n >> m;
	floydWarshall();
}