BOJ 16681 등산(Python 3)

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

엄청나게 고통 받은 문제다..

heapq로 풀면 시간 초과,,, deque로 풀면 메모리 초과,,,

메모리 초과는 암만 생각해봐도 잘못된 풀이 방법이기에 heapq에 집중하기로 했다.

다익스트라를 따로 공부한게 아니라 heapq로 저런 알고리즘을 구현 할 수 있다는 생각으로 문제를 풀기 시작했기 때문에 개념에 구멍이 숭숭 뚫려있는 상태였는데, 이 문제를 풀고 완벽하게 다익스트라를 구현 할 수 있게 되었다.

그동안 풀은 다익스트라 문제는 간선의 수가 작아서 운 좋게 통과한 듯 싶다.
(heappop에서 리스트의 값이랑 일치하지 않는 값이 나오면 continue를 해야하는데, 나는 이걸 모른 상태로 풀어왔다)

간단하게 1에서부터 n까지의 최소 체력을 구하기 위해 1부터 출발하는 다익스트라를 구현하고, n부터 출발하는 다익스트라를 구현한 후 가치의 최댓값을 구하면 되는 문제다.

입력하는 값이 많기 때문에 시간 초과를 받을지도 몰라 sys.stdin.readline으로 값을 받았다.

코드 확인

def Dijkstra(G,A):
    G[A]=0
    q=[]
    heappush(q,[0,A])
    while q:
        t,x=heappop(q)
        if G[x]!=t:continue
        for nx,nt in D[x]:
            if K[nx]>K[x] and G[nx]>nt+t:
                G[nx]=nt+t
                heappush(q,[nt+t,nx])
from heapq import *
input=__import__('sys').stdin.readline
n,m,d,e=map(int,input().split())
K=[0]+[*map(int,input().split())]
D=[[] for _ in range(n+1)]
ans=-float('INF')
for i in range(m):
    a,b,c=map(int,input().split())
    D[a].append((b,c))
    D[b].append((a,c))
X=[float('INF')]*(n+1)
Dijkstra(X,1)
Y=[float('INF')]*(n+1)
Dijkstra(Y,n)
for i in range(1,n+1):
    k=K[i]*e-(X[i]+Y[i])*d
    if k>ans:ans=k
print([ans,'Impossible'][ans==-float('INF')])