11779_최소비용 구하기 2

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

11779번: 최소비용 구하기 2

 

 

 

이전의 다익스트라 알고리즘을 활용하면 풀 수 있다.

 

이전과 다른점은 어디를 방문했는지 기록을 해둬야 할것이다.

 

그래서 visited란 배열을 하나 만든 후에, 새로운 노드에 값을 기록할때마다 어느 노드에서 왔는지 기록하도록 하였다.

 

 

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1)]

for _ in range(m):
    s,e,v = map(int,input().split())
    graph[s].append((e,v))
start,end = map(int,input().split())

dist = [ INF for _ in range(n+1) ]
visited = [ 0 for _ in range(n+1)]

q = []
heapq.heappush(q,(0,start))
while q:
    cnt,node = heapq.heappop(q)

    if dist[node] < cnt:
        continue
    if node == start:
        dist[node] = 0

    for next,value in graph[node]:
        if dist[next] > cnt + value:
            dist[next] = cnt + value
            visited[next] = node
            heapq.heappush(q,(cnt+value,next))

print(dist[end])
result = [end]
tmp = visited[end]
while tmp != 0:
    result.append(tmp)
    tmp = visited[tmp]
result.reverse()
print(len(result))
print(*result)

 

 

이때 처음에는 if문 두개를 두지 않아 메모리 초과가 계속해서 발생하였다.

 

알고보니 해당 조건으로 q를 계속 없애주지 않으면 q가 계속해서 쌓이게 되어 없애주는 구조로 만들어줘야 통과할 수 있었다. 같은 원리로 deque를 이용하지 않고 최소힙을 사용해야 했다.