[백준] 1916 최소비용 구하기 (파이썬 python)

 

 

문제 링크

 

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

1916번: 최소비용 구하기

 

 

 

문제 풀이

 

한 지점에서 다른 특정 지점까지의 최단 거리를 구하는 문제로

heapq를 통한 다익스트라 알고리즘을 구현하여 풀이했습니다.

 

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(start):
    q = []
    distance[start - 1] = 0
    heappush(q, (0, start - 1))
    while q:
        dist, now = heappop(q)
        if distance[now] < dist:
            continue
        for end, weight in graph[now]:
            weight += dist
            if weight < distance[end]:
                distance[end] = weight
                heappush(q, [weight, end])

n = int(input())
m = int(input())
graph = [[] for _ in range(n)]
distance = [1e9] * n
for _ in range(m):
    s, e, w = map(int, input().split())
    graph[s - 1].append((e - 1, w))
start, end = map(int, input().split())
dijkstra(start)
print(distance[end - 1])

 

 

문제의 제한 시간이 0.5초로 짧은 편인데 계속해서 시간 초과가 걸려 난감했습니다.

처음에 작성한 코드에서는 weight + dist를 처음에 한 번만 해주는게 아니라

매번 사용할 때마다 해주었는데 (한 번의 for문당 3번의 연산)

연산처리가 너무 많이 이루어진 탓에 시간 초과가 났습니다.

반복되는 구문을 줄이는 것도 중요하다는 것을 느꼈습니다.

 

        for end, weight in graph[now]:
            weight += dist
            if weight < distance[end]:
                distance[end] = weight
                heappush(q, [weight, end])