반응형

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

 

23286번: 허들 넘기

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

1. arr[ N ][ N ] 배열을 만들어서 값을 987654321로 초기화해 줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 이동 구간 중 가장 높은 허들의 높이가 가장 낮은 값으로 arr 배열을 갱신합니다.

 

3. arr[ u ][ v ]의 값이 987654321이라면 -1을 아니라면 arr[ u ][ v ]를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
 
using namespace std;
 
int N, M, T;
int arr[301][301];
 
int main()
{
    scanf("%d %d %d", &N, &M, &T);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            arr[i][j] = 987654321;
        }
    }
 
    for (int i = 0; i < M; i++) {
        int u, v, h;
        scanf("%d %d %d", &u, &v, &h);
 
        arr[u][v] = h;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                arr[j][k] = min(arr[j][k], max(arr[j][i], arr[i][k]));
            }
        }
    }
 
    for (int i = 0; i < T; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        if (arr[u][v] == 987654321) {
            printf("-1\n");
        }
        else {
            printf("%d\n", arr[u][v]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22

+ Recent posts

티스토리툴바