[BOJ/Gold 2] 백준 23286 허들 넘기(C++)

문제 링크

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

23286번: 허들 넘기

 

문제

허들 국가대표를 꿈꾸는 연두는 그래프 위에서 허들 넘기를 연습하려고 한다. 연두가 연습할 그래프는 정점이 N개 있고, 간선이 M개 있다. 간선은 방향성이 있어, 1에서 2로 가는 길이 있더라도, 2에서 1로 가는 길은 없을 수도 있다. 간선 위에는 허들이 중간에 놓여 있고, 간선을 지나갈 때는 반드시 허들을 넘어야 한다.

연두는 연습을 T번 할 것이고, 각 연습마다 출발 정점과 도착 정점을 미리 정해놓았다. 연두가 힘들지 않게 연습을 하기 위해, 각 연습마다 출발 정점에서 도착 정점으로 가는 경로 중에서 가장 높이가 높은 허들의 높이가 최소가 되는 것을 찾아보자.

입력

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 줄에는 연습의 정보 s, e가 한 줄에 하나씩 주어진다. s는 출발 정점, e는 도착 정점을 의미한다.

출력

입력으로 주어진 연습 마다 한 줄에 하나씩 출발 정점에서 도착 정점으로 가는 경로 중 가장 높은 허들 높이의 최솟값을 출력한다. 만약 출발 정점에서 도착 정점으로 갈 수 없는 경우 -1을 출력한다.

제한

• 1 ≤ N ≤ 300
• 1 ≤ M ≤ 25,000
• 1 ≤ T ≤ 40,000
• 1 ≤ u, v ≤ N
• u ≠ v
• 1 ≤ h ≤ 1,000,000
• 1 ≤ s, e ≤ N
• s ≠ e

예제 입력 1

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

예제 출력 1

4
8
-1

 

알고리즘 분류

• 최단 거리 알고리즘

풀이

플로이드-와샬을 응용하여, i부터 j까지 갈 때의 허들이 더 낮은지, 아니면 k를 경유해서 갈 때의 허들이 더 낮은지를 기록한다. 이 방식대로 해도 정점이 최대 300개이기 때문에 시간 제한에 걸리지 않는다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 301
#define LL long long
#define INF 1e9

using namespace std;
int N, M, T;
int DP[MAX][MAX];

void Input() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				continue;
			}
			DP[i][j] = INF;
		}
	}
	for (int i = 0; i < M; i++) {
		int U, V, H;
		cin >> U >> V >> H;
		DP[U][V] = H;
	}
}

void Settings() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				DP[i][j] = min(DP[i][j], max(DP[i][k], DP[k][j]));
			}
		}
	}
}

void Query() {
	for (int i = 0; i < T; i++) {
		int S, E;
		cin >> S >> E;
		if (DP[S][E] == INF) {
			cout << -1 << "\n";
		}
		else {
			cout << DP[S][E] << "\n";
		}
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Query();

	return 0;
}