본문 바로가기
카테고리 없음

백준 16681번 등산

by Shark_상어 2023. 1. 31.
728x90

문제

문제링크

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

  1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
  2. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
  3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
  4. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
  5. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

입력

첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤  E ≤ 100)

두 번째 줄에 N개의 정수 h1, ...  ,hN이 공백으로 구분되어 주어진다. hi는 i 번째 지점의 높이를 의미한다. (1 ≤ hi ≤ 1,000,000, 1 ≤ i ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 세 정수 a, b, n이 공백으로 구분되어 주어진다. 이는 a번 지점과 b번 지점을 잇는 거리 n의 양방향 경로가 있음을 의미한다. (1 ≤ a, b ≤ N, 1 ≤ n ≤ 100,000)

어떤 지점에서 다른 지점으로 가는 경로가 여러 개 있을 수도 있으며 (등산로는 여러 개가 있을 수 있다), 한 지점에서 출발해 그 지점으로 돌아가는 경로가 있을 수도 있다 (쉼터에서 몇 바퀴 돌며 쉴 수도 있다).

주환이의 집은 1번 지점에 위치하고, 고려대학교는 N번 지점에 위치하며 주환이의 집과 고려대학교의 높이는 1임이 보장된다.

출력

첫 번째 줄에 주환이가 얻을 수 있는 가치의 최댓값을 출력한다. 만약 조건을 만족하는 등산 경로를 선택할 수 없다면, "Impossible"을 쌍따옴표를 제외하고 출력한다. 답이 음수일 수 있음에 유의하여라.

2. 코드

import sys
from heapq import heappush, heappop

INF = sys.maxsize
input = sys.stdin.readline

def dijstra(start):
    dis = [INF] * (n + 1)
    dis[start] = 0

    queue = []
    heappush(queue, (0, start))

    while queue:
        dist, now = heappop(queue)

        if dis[now] < dist:
            continue

        for i in maps[now]:
            cost = dist + i[1]

            # 집에서 시작해서 높은 곳으로만 갈곳!
            # 고려대에서 시작해서 높은 곳으로만 갈곳!
            if cost < dis[i[0]] and high[now] < high[i[0]]:
                dis[i[0]] = cost
                heappush(queue, (cost, i[0]))

    return dis

# 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량
n, m, d, e = map(int, input().split())

# 등산 높이
high = [0] + list(map(int, input().split()))

maps = [[] for _ in range(n + 1)]

# 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    maps[a].append((b, c))
    maps[b].append((a, c))

# 집에서 모든 지점을 최소 값으로 이동
S = dijstra(1)

# 고려대에서 모든 지점을 최소 값으로 이동
E = dijstra(n)

# 등산의 가치
ans = -INF

# 집 과 고려대를 제외하고 가치값 찾기
for i in range(2, n):
    ans = max(ans, high[i] * e - (S[i] + E[i]) * d)
if ans == -INF:
    print("Impossible")
else:
    print(ans)

3. 회고

Q. 문제를 보고 든 생각

  • 설명만 엄청 길지 사실상 말하는 것은 집에서 고려대까지 갈수 있는 최소 비용 + 고려대 에서 집으로 갈수 있는 최소 비용 으로 가는도중 성취감을 최대로 얻을수 있는 등산코스가 무엇이냐?? 라고 물어 보는문제이다.
  • 그럼으로 일반적인 다익스트라에서 등산은 낮은 높이에서 높은 곳 이동하는 것만 코드로 작성 해주면 된다.

4. 고쳐야 할점

문제의 핵심을 반드시 기억하자

728x90

티스토리툴바