[백준] 1753. 최단경로 (Python)

link 🔗 https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

🔥 기본적인 다익스트라 문제인 것 같다

 

import heapq
import sys

V, E = map(int, sys.stdin.readline().split())

snum = int(sys.stdin.readline())

board = [[] for _ in range(V+1)]

result = [2e18]*(V+1)

def dijkstra(start):
    heap = []
    result[start] = 0
    heapq.heappush(heap, (0, start)) # 비용, 경유지
    while heap:
        kycost, ky = heapq.heappop(heap)
        if kycost > result[ky]:
            continue
        for b in board[ky]:
            gokycost = kycost+b[0]
            if gokycost < result[b[1]]:
                result[b[1]] = gokycost
                heapq.heappush(heap, (gokycost, b[1]))

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    board[u].append((w, v)) # 비용, 도착지

dijkstra(snum)

for idx in range(1, V+1):
    if result[idx] == 2e18:
        print('INF')
    else:
        print(result[idx])