[Python 3] BOJ - 16681 "등산"

 # 문제 링크

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

16681번: 등산

 

 # 풀이

 개인적으로 이 문제의 핵심은 대칭성을 이용하는 것이다. 문제에서 집에서 목표까지는 높이가 증가하는 방향, 목표에서 학교까지는 높이가 감소하는 방향으로 가는 조건이 있다. 따라서 학교에서 높이까지는 높이가 증가하는 방향이라고 할 수 있다. 그런데 집-목표-학교의 최소 거리는 집-목표 + 목표-학교의 각각의 최소 거리의 합보다 더 작을 수 없다.

 따라서, 높이가 증가하는 경우에만 동작하는 다익스트라를 만든 후, 집과 학교를 출발점으로 했을 때 둘 중 하나라도 임의의 목표에 도달할 수 없다면, 즉 학교-목표의 거리도 INF거나 집-목표의 거리도 INF라면 그 목표는 절대 도달할 수 없다. 따라서 그런 경우가 아닌 목표에 대해서 얻을 수 있는 가치의 최대값을 출력하면 된다. 만일 모든 임의의 목표점이 전부 도달할 수 없다면 Impossible을 출력하면 정답을 시간안에 구할 수 있다

 

 # 코드

import sys, heapq

# dijkstra : 출발지 num에서 출발하여 높이가 증가하는 순서대로 최단거리 갱신 후, 최단거리 배열을 리턴하는 함수 
def dijkstra(num):
    d = [inf] * (n + 1)
    d[num] = 0
    q = []
    heapq.heappush(q, (0, num))
    while q:
        cur_dist, cur = heapq.heappop(q)
        if d[cur] < cur_dist:
            continue
        for (next, next_dist) in adj[cur]:
            # 만일 높이가 높다면 진행
            if arr[next] > arr[cur]:
                if d[next] > next_dist + cur_dist:
                    d[next] = next_dist + cur_dist
                    heapq.heappush(q, (next_dist + cur_dist, next))
    return d

# 입력부
n,m,d,e = map(int, sys.stdin.readline().split())
arr = [-1] + list(map(int, sys.stdin.readline().split()))
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a,b,c = map(int, sys.stdin.readline().split())
    adj[a].append((b,c))
    adj[b].append((a,c))

# inf : 무한대값
inf = 98765432109876543210

# res1 : 집에서 각 목표까지의 최단거리 배열
res1 = dijkstra(1)
# res2 : 학교에서 각 목표까지의 최단거리 배열
res2 = dijkstra(n)
ans = []
for i in range(1, n + 1):
    # 만일 두 지점에서 갈 수 있다면 정답배열에 가치를 추가
    if res1[i] != inf and res2[i] != inf:
        ans.append(arr[i] * e - d * (res1[i] + res2[i]))

# 정답 출력
print(max(ans) if ans else 'Impossible')