[백준 1753] 최단경로

문제

 

www.acmicpc.net/problem/1753

1753번: 최단경로

 

처음 작성한 코드

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
INF = sys.maxsize
graph = [INF] * (V+1)
queue = []
arr = {i+1:[] for i in range(V)}

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    arr[u].append([v, w])

heapq.heappush(queue, [0, start])
graph[start] = 0

while queue:
    w, now = heapq.heappop(queue)
    for i in arr[now]:
        if graph[i[0]] > w+i[1]:
            graph[i[0]] = w+i[1]
            heapq.heappush(queue, [graph[i[0]], i[0]])

for i in range(1, V+1):
    print(graph[i] if graph[i]!=INF else 'INF')

 

깨달은 점

• 시간초과 5번 났는데 이유를 찾았다. 가중치가 변경될때만 queue에 넣어야하는데 안변경되도 queue에 넣어가지고 똑같은 점을 엄청 많이 방문하고 있었다....... 
• sys.maxsize를 알게됐다.
• heapq는 heap구조를 유지하며 push, pop 해주는 내장모듈인데 신기하다..