[BOJ 6135 // C++] Cow Hurdles

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6135번 문제인 Cow Hurdles이다.
문제는 아래 링크를 확인하자.

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

6135번: Cow Hurdles

각 점에서 다른 점으로의 이동경로 중 "가장 높은 허들이 있는 간선"의 허들의 높이가 가장 낮은 경우의 그 허들의 높이를 구하는 문제이다. 존재하는 두 노드쌍의 수에 비해 쿼리의 수가 상당히 많으므로, 모든 가능한 노드쌍에 대하여 답을 미리 구해두는 전처리를 해보는 것을 고려할 수 있다.

 

전처리를 하는 방법 중 하나로, Floyd-Warshall 알고리즘에서 각 노드 u, v 사이에 다른 경로 k를 경유하는 경우를 살펴보면서 u, v 사이의 최단거리를 알아내듯이 u와 v 사이의 경로에서의 가장 높은 허들의 높이의 최솟값 또한 알아내는 방법이 있다. Floyd-Warshall의 증명을 알고 있다면 위와 같은 방식이 통하는 이유 또한 쉽게 알 수 있을 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int dist[301][301];

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

	memset(dist, 0x3f, sizeof(dist));

	int N, M, T; cin >> N >> M >> T;
	while (M--) {
		int x, y, d; cin >> x >> y >> d;
		dist[x][y] = d;
	}

	for (int i = 1; i <= N; i++) dist[i][i] = 0;

	for (int k = 1; k <= N; k++) {
		for (int x = 1; x <= N; x++) {
			for (int y = 1; y <= N; y++) {
				dist[x][y] = min(dist[x][y], max(dist[x][k], dist[k][y]));
			}
		}
	}

	while (T--) {
		int x, y; cin >> x >> y;
		int& ans = dist[x][y];
		if (ans == 1061109567) cout << -1 << '\n';
		else cout << dist[x][y] << '\n';
	}
}