BOJ1916 최소비용 구하기

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

1916번: 최소비용 구하기

 

난이도: 골드5

소요시간: 45분, hint

 

문제자체는 다익스트라 유형의 기본문제이다. 다만 제한시간이 0.5초로 매우 짧다.

처음 풀었을 때는 메모리초과가 떴다. 이 문제는 약간 수정하니 해결되었다.

정말 문제는 시간 초과이다. 이 문제를 해결하기 위해서 리스트에서 인덱스접근하는것을 변수로, 중간에 조건으로 브랜치 등을 하였지만 해결이 되지 않았다. 결국 해결한 방법은  아래의 코드를 힙팝한 이후에 바로 검사하는 것이다. 아래 코드의 의미는 dist[node]의 값이 바뀌었으면 뛰어넘으란 말인데 dist[node]의 값이 바뀌었다는 것은 힙에 들어간 시기가 node값이 최소값으로 바뀌기 전이라는 뜻이다. 그러므로 확인을 해줄필요가 없다. 

if dist[node] < distance:
    continue

아래는 나의 코드이다. 위의 조건문을 안넣어도 풀리는 문제가 많았어서 나도 모르게 저 조건을 빼는 것이 습관이 되었다. 위의 코드를 빠뜨리지 않도록 하여야겠다.

#10:35 골드5 45분,hint(시간초과)

import sys
import heapq
INF=1e9
N = int(sys.stdin.readline())
M= int(sys.stdin.readline())
graph=[[]for _ in range(N+1)]
dist=[INF]*(N+1)
dist[0] = 0
for i in range(M):
    start,end,cost=map(int,sys.stdin.readline().split())
    graph[start].append([end,cost])
    graph[end].append([end,cost])

start,end = map(int,sys.stdin.readline().split())

def daijkstra(start):
    hq=[]
    dist[start]=0
    heapq.heappush(hq,[0,start])
    while hq:
        distance,node=heapq.heappop(hq)
        if dist[node] < distance:
            continue
        for next_node,next_cost in graph[node]:
            if dist[next_node] <next_cost:
                continue
            if dist[next_node] > distance+next_cost:
                dist[next_node] = distance+next_cost
                heapq.heappush(hq,[distance+next_cost,next_node])

daijkstra(start)
print(dist[end])