(BOJ23286 허들 넘기

• tags : (algorithm

  No matching post could be found

  - (floyd-warshall
• 문제 링크 : https://www.acmicpc.net/problem/23286
• 풀이 링크
  • Python

• 문제에서는 허들이라고 했지만, 그래프를 구성하는 간선의 최댓값을 최소화하는 문제이다.
• 생성된 그래프에서 플로이드와샬로 간단하게 해결했다.

N, M, T = MIIS()
hurdles = [[-1] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    u, v, h = MIIS()
    hurdles[u][v] = h
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if hurdles[i][k] == -1 or hurdles[k][j] == -1:
                continue
            max_hurdle = max(hurdles[i][k], hurdles[k][j])
            if hurdles[i][j] == -1 or hurdles[i][j] > max_hurdle:
                hurdles[i][j] = max_hurdle
for _ in range(T):
    s, e = MIIS()
    print(hurdles[s][e])

• 코드가 길지 않아 전체 코드를 가져왔다.
• 각 간선은 방향이 있어 방향에 따라 저장했다.
• 거쳐가는 점, 출발 점, 도착 점을 순서대로 for문으로 순회하였고
  • 연결할 수 있고, 새로운 연결이거나, 허들 높이가 낮아지는 경우 최신화했다.
• 출력은 출발, 도착점 기준으로 바로 출력할 수 있기 때문에 짧은 코드로 해결할 수 있었다.