백준 / 11779 / 최소비용 구하기 2 / python

import sys
input = sys.stdin.readline

from heapq import heappop, heappush
from collections import deque

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
distance = [1e9] * (n+1)

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

start, end = [int(v) for v in input().split()]

q = []
heappush(q, [0, [start]])
distance[start] = 0

m = 1e9
result = []
while q:
    v, node = heappop(q)
    # print("v = ",v, " node = ", node)
    if distance[node[-1]] < v:
        continue
    
    if node[-1] == end and v < m:
        result = node

    for next_node, next_v in graph[node[-1]]:
        d = v + next_v
        if distance[next_node] > d:
            distance[next_node] = d
            heappush(q, (d, node + [next_node]))

print(distance[end])
print(len(result))
print(*result)

정답이긴 하지만 이 방식은 노드를 계속해서 저장하고 있으므로 메모리를 비효율적으로 사용하게 된다. 이전에 사용한 방법처럼 지나온 경로를 저장하는 리스트를 사용하는 방식으로 해결

import sys
input = sys.stdin.readline

from heapq import heappop, heappush
from collections import deque

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
distance = [1e9] * (n+1)

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

start, end = [int(v) for v in input().split()]

q = []
heappush(q, [0, start])
distance[start] = 0
result = [0] * (n+1)

m = 1e9
while q:
    v, node = heappop(q)
    # print("v = ",v, " node = ", node)
    if distance[node] < v:
        continue
    
    for next_node, next_v in graph[node]:
        d = v + next_v
        if distance[next_node] > d:
            distance[next_node] = d
            result[next_node] = node
            heappush(q, (d, next_node))

print(distance[end])

tmp = result[end]
r = [end]
while tmp != start:
    r.append(tmp)
    tmp = result[tmp]
r += [start]
print(len(r))
print(*r[::-1])

후 방법이 메모리와 시간 면에서 좀더 효율적인걸 볼 수 있다.