[백준] 1753번

필요한 사전지식

heapq (priority queue) 알고리즘을 제공

힙 함수 활용

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.

problem

최단경로 구하는 문제

solution

code

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

import heapq
n,m = map(int,input().split()) #정점 수, 간선 수
k = int(input()) #시작 정점 번호

graph = [[]*(n+1) for _ in range(n+1)]
#print(graph)
INF = int(1e9)
distance = [INF] *(n+1)

for _ in range(m):
    u,v,w = map(int,input().split()) #u->v, 가중치
    graph[u].append((v,w))# (도착점, 가중치)
#print(graph)

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start)) # heap에 (최단거리, 시작점) 추가
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist+i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
                
                
dijkstra(k)

for i in range(1,n+1):
    if distance[i]== INF:
        print("INF")
    else:
        print(distance[i])