[백준] 최소비용 구하기

# Practice : dijkstra

import heapq

n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
costs = [float("inf")] * (n + 1)  # 각 노드까지 가는 데 드는 비용 테이블


for _ in range(m):
    i, j, cost = map(int, input().split())
    graph[i].append((j, cost))

# print(graph)


def dijkstra(start):
    global costs
    queue = []
    costs[start] = 0
    heapq.heappush(queue, (0, start))
    while queue:
        for _ in range(len(queue)):
            accum_cost, present_node = heapq.heappop(queue)
            if costs[present_node] < accum_cost:
                continue

            for next_node, cost in graph[present_node]:
                heapq.heappush(queue, (accum_cost + cost, next_node))
                if costs[next_node] > accum_cost + cost:
                    costs[next_node] = accum_cost + cost
            # print(costs)


start, end = map(int, input().split())

dijkstra(start)

# print(costs)

print(costs[end])

메모리 초과가 나는 이유는?

1. heapq.heappush(queue, (accum_cost + cost, next_node)) 위치가 잘못됐음
   저 위치에 넣으면 cost가 갱신되든 안되든 일단 넣는다는 의미니까 힙이 불필요하게 커짐
2. float 대신 int쓰는게 좋음 (보통 10**15 많이씀) 1e15도 float이니까 조심
3. 추가 팁) 지금 이 문제처럼 특정 도착지를 명시한 경우, 다음과 같이 도착지가 등장하자마자 return해버려도 됨

def dijkstra(start, end):
    global costs
    queue = []
    costs[start] = 0
    heapq.heappush(queue, (0, start))
    while queue:
        accum_cost, present_node = heapq.heappop(queue)
		if present_node == end:
        	return accum_cost
        
        if costs[present_node] < accum_cost:
            continue

        for next_node, cost in graph[present_node]:
            heapq.heappush(queue, (accum_cost + cost, next_node))
            if costs[next_node] > accum_cost + cost:
                costs[next_node] = accum_cost + cost


start, end = map(int, input().split())

dijkstra(start, end)