1. 문제 설명

등산

2. 문제 분석

다익스트라 알고리즘을 통해 집에서 목표까지의 최단 거리를 구하자. 학교에서 목표까지의 최단 거리 또한 구할 수 있다. 특정 목표를 경유지로 사용할 수 있다면 (즉 다익스트라로 얻어낸 거리값이 무한대가 아닐 때) 성취감과 거리값의 차 중 최댓값을 구할 수 있다.

• 다익스트라를 통해 접근하는 건 곧바로 알 수 있었는데, 경유지 최단 거리를 얻을 때 학교에서 거꾸로가 아니라 집에서 목표까지 구한 뒤, 목표에서 학교까지의 다익스트라를 돌렸기 때문에 시간 초과가 났다. 당연히 학교를 시작 노드로 한 다익스트라 알고리즘으로 얻은 거리값 리스트로 한 번에 처리할 수 있었는데, 일종의 고정 관념에 사로 잡혀 있었나.

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize
n, m, d, e = map(int, sys.stdin.readline().rstrip().split())
heights = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])

def Dijkstra(start):
    distances = [INF for _ in range(n+1)]
    distances[start] = 0

    pq = []
    heapq.heappush(pq, [0, start])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)

        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if heights[cur_node] < heights[next_node] and distances[next_node] > cur_cost + next_cost:
                # 높이에 따라 이동 가능
                distances[next_node] = cur_cost + next_cost
                heapq.heappush(pq, [cur_cost + next_cost, next_node])

    return distances

dist_start = Dijkstra(1)
dist_goal = Dijkstra(n)
ans = -INF
for idx in range(2, n):
    d1, d2 = dist_start[idx], dist_goal[idx]
    # 집 -> idx (목표) -> 학교 이동 최소 거리
    if d1 == INF or d2 == INF: continue
    # INF면 이동 불가능한 목표
    ans = max(ans, heights[idx]*e - (d1 + d2) * d)

if ans == -INF: print("Impossible")
else: print(ans)