백준 16681번: 등산

백준 16681번: 등산

풀이 과정

경로 탐색 과정에서 높이가 증가할 때만 큐에 푸쉬해주는 집에서 출발하는 다익스트라와 고려대학교에서 출발하는 다익스트라를 실행한다. 그러면 문제가 원하는, 목적지까지는 높아지고 이후로는 낮아지는 경로가 나온다.

정답 코드

import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline


def dijkstra(S):
    Q = list()
    heappush(Q, (0, S))

    D = [float('inf')] * (N + 1)
    D[S] = 0

    while Q:
        SD, SN = heappop(Q)

        if D[SN] < SD:
            continue

        for FN, FD in L[SN]:
            d = SD + FD
            if D[FN] > d and H[SN] < H[FN]:
                D[FN] = d
                heappush(Q, (d, FN))
                
    return D


N, M, D, E = map(int, input().split())
H = [0] + list(map(int, input().split()))
L = defaultdict(list)
for i in range(M):
    a, b, n = map(int, input().split())
    L[a].append((b, n))
    L[b].append((a, n))

S = dijkstra(1)
F = dijkstra(N)
MAX = - float('inf')
for i in range(2, N):
    MAX = max(MAX, H[i] * E - (S[i] + F[i]) * D)
print(MAX if MAX != - float('inf') else "Impossible")